Question

implement c++ Quicksort using median of 3 as pivot. this also pass comparator as a function param so it can sort vector in increasing or decreasing order based on the comparator passed. the test code uses std::less comparator.

#ifndef QSORT_H

#define QSORT_H

#include

#include

using namespace std;

template

T median_of_three(T& a, T& b, T& c, TComparator comparator) {

}

template

size_t partition(vector& vec, TComparator& comparator, size_t low, size_t high) {

// TODO: implement.

}

template

void QuickSort(vector& vec, TComparator comparator,size_t low,size_t high) {

if(comparator(low,high)){

size_t loc = partition(vec,comparator,low,high);

QuickSort(vec,comparator,low,loc-1);

QuickSort(vec,comparator,loc+1,high);

}

return;

}

template

void quicksort(vector& vec, TComparator comparator) {

// TODO: implement.

size_t size = vec.size();

QuickSort(vec,comparator,0,size-1);

}

#endif

test_case:

int main() {

srand(time(NULL));

vector test;

for (int i =0; i < 10; i++) {

test.push_back(rand() % 1000);

}

for (int i = 0; i < 10; i++) {

cout << test[i] << " ";

}

cout<<"Before sort;"<

quicksort(test, std::less {});

for (int i = 0; i < 10; i++) {

cout << test[i] << " ";

}

cout << endl;

return 0;

}

Answer 1

#include <iostream>
#include<algorithm>
using namespace std;
#define size 10
int i;   
void show(int* array, int n);
int partition(int* array, int pValue, int left, int right);
void QuickSort(int* array, int left, int right);

int main(void)
{
int array[size];
int i;

for( i = 0; i < size; i++)
{
array[i]=rand()%100;
}

cout<<endl<<"The random generated numbers are: "<<endl;
show(array, size);
QuickSort(array,0,size - 1);
cout<<endl<<"The sorted numbers are : "<<endl;
show(array, size);

system("pause");
return 0;
}

void show(int* array, int n)
{
int i;

for( i = 0; i < n; i++) cout<<array[i]<<'\t';
}

void QuickSort(int* array, int left, int right)
{
for(i=0;i<3;i++)
{
array[i]=array[rand()%100];
}
stable_sort(array,array+3);
int p=array[(i+1)/2];
//int p = array[left];
int split;

if(right > left)   
{
split = partition(array, p, left, right);

array[split] = p;
QuickSort(array, left, split-1);   
QuickSort(array, split+1, right);
}
}

int partition(int* array, int p, int left, int right)
{
int lb = left;
int rb = right;

while(lb < rb)   
{
while( p < array[rb]&& rb > lb)
{
rb--;   
}
swap(array[lb], array[rb]);

while( p >= array[lb]&& lb < rb)   
{
lb++;
}
swap(array[rb], array[lb]);

}
return lb;

}