Create a Program to Implement Sorting Technique in C++ Assignment Solution

Instructions

Objective

Write a C++ homework program to implement sorting technique.

Requirements and Specifications

Source Code

#include #include #include #include using namespace std; // Swap two elements that is in the list void swap(vector &list, int i, int j) { int temp = list[i]; list[i] = list[j]; list[j] = temp; } // Get the median of 3 int getMedianOf3(vector &list, int left, int right) { int center = (left + right) / 2; if (list[left] > list[center]) { swap(list, left, center); } if (list[left] > list[right]) { swap(list, left, right); } if (list[center] > list[right]) { swap(list, center, right); } swap(list, center, right - 1); return list[right - 1]; } // Partition using median of 3 int partition(vector& list, int first, int last) { // The pivot should be the median of the // first, middle, and last elements. int median = getMedianOf3(list, first, last); int left = first; int right = last - 1; while (true) { while (list[++left] < median) { } while (list[--right] > median) { } if (left >= right) { break; } swap(list, left, right); } swap(list, left, last - 1); return left; } // Do insertion sort on a particular partition only, this is only called // when it is impossible to use median of 3 of a particular partition // because in a median of 3 it requires at least 3 numbers. void insertionSort(vector &list, int left, int right) { // sorted on left of out for (int i = left + 1; i <= right; i++) { int number = list[i]; int j = i; while (j > left && list[j - 1] >= number) { list[j] = list[j - 1]; --j; } list[j] = number; } } // Do a quick sort on the vector void quicksort(vector& list, int first, int last) { int size = last - first + 1; if (size <= 3) { // Can't do partitioning using median of 3 anymore if there's just 3, so we sort the // last remaining partition with regular sort insertionSort(list, first, last); } else { // Continue partitioning with the median of 3. int p = partition(list, first, last); quicksort(list, first, p - 1); quicksort(list, p + 1, last); } } // Debug function to check if list is sorted void printList(vector &list) { for (unsigned i = 0; i < list.size(); i++) cout << list[i] << " "; cout << endl; } // Do the multi-way sort void multiway_merge(vector >& input_lists, vector& output_list) { // Now merge each sub-lists as one // Initially put the first elements of the input list in the priority queue priority_queue, greater > queue; for (unsigned i = 0; i < input_lists.size(); i++) if (!input_lists.empty()) queue.push(input_lists[i][0]); while (!queue.empty()) { // Extract the next lowest element from the priority queue int next = queue.top(); queue.pop(); output_list.push_back(next); // Remove the next value to which sublist it came from and // replace with the successor for (unsigned i = 0; i < input_lists.size(); i++) { if (!input_lists[i].empty() && input_lists[i][0] == next) { // Found it! input_lists[i].erase(input_lists[i].begin()); if (!input_lists[i].empty()) queue.push(input_lists[i][0]); break; } } } } // Entry point of the program int main(int argc, char** argv) { int n, m; cin >> n >> m; vector > input_lists(n, vector(m)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> input_lists[i][j]; // Quicksort k sublists for (unsigned i = 0; i < input_lists.size(); ++i) quicksort(input_lists[i], 0, m - 1); // Merge n input sublists into one sorted list vector output_list; multiway_merge(input_lists, output_list); for (unsigned i = 0; i < output_list.size(); ++i) cout << output_list[i] << " "; cout << endl; return 0; }