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

July 15, 2024
Sarah Rodriguez
🇺🇸 United States
C++
Sarah is a skilled C++ programmer with a Master's degree in Computer Engineering. She specializes in data abstraction, encapsulation, and constructor and destructor functions. With over 600 completed assignments, Sarah's attention to detail and commitment to excellence ensure that students receive well-structured and reliable solutions for their Classes and Top-down Design tasks.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

## 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; } ```

## Related Samples

View our free C++ assignment samples for a clear perspective on programming concepts. These samples provide detailed solutions and practical examples, showcasing the application of C++ in various scenarios. Each sample is crafted to help you grasp complex topics more effectively, making your learning process smoother and more efficient. Access these resources to gain valuable insights into C++ programming and excel in your assignments.