Instructions
Objective
Write a C++ homework program to implement sorting technique.
Requirements and Specifications
![program to implement sorting technique in C++](https://www.programminghomeworkhelp.com/uploads/images/program-to-implement-sorting-technique-in-C++.webp)
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.
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++