+1 (315) 557-6473 

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

program to implement sorting technique in C++

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;

}