//**************************************************************************** // Programmer: Sriram Pemmaraju // Date: 8/27/2002 // This program reads a sequence of non-negative integers from the input and // writes them back to the output in sorted order, with duplicates removed. //**************************************************************************** #include #include using namespace std; // This function reads the list of numbers given as input; it expects the // size of the list to be given as an argument // Postcondition: After the function is executed, numberList // contains the list of numbers given as input void readNumbers(int* numberList, int number){ for (int i = 0; i < number; i++) cin >> numberList[i]; } // This function sorts a list of numbers using bubblesort // Precondition: numberList is an array of size number // Postcondition: The elements in numberList are in non-decreasing order void sort(int* numberList, int number){ for(int i = 0; i <= number-2 ; i++) for(int j = number-2; j >=i; j--){ if(numberList[j] > numberList[j+1]){ int t = numberList[j]; numberList[j] = numberList[j+1]; numberList[j+1] = t; } } } // In a sorted list of numbers, this function replaces by -1 all except the // last element in a block of identical elements // Precondition: numberList is a sorted integer array of size number // Postcondition: For every block of identical elements in numberList, all // except the last element are replaced by -1 void scanAndMark(int* numberList, int number){ for(int i = 0; i < number-1; i++) if(numberList[i]==numberList[i+1]) numberList[i] = -1; } // This function takes a list that contains some -1s and a bunch of non-negative // integers and moves the non-negative integers to the left so that they form a // contiguous block. The function then returns the number of non-negative // integers in the list. // Precondition: numberList is an integer array of size number // Postcondition: All non-negative integers occur in the beginning of the array int makeCompact(int* numberList, int number){ int count = 0; for(int i = 0; i < number; i++) if(numberList[i] == -1) count++; else numberList[i-count] = numberList[i]; return number-count; } int main(){ int number; cin >> number; int numberList[number]; readNumbers(numberList, number); sort(numberList, number); scanAndMark(numberList, number); number = makeCompact(numberList, number); cout << "List without duplicates" << endl; for (int i = 0; i < number; i++) cout << numberList[i] << " "; cout << endl; return EXIT_SUCCESS; }