Question

implement c++ Quicksort using median of 3

#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<int> 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;"<<endl;

quicksort(test, std::less<int> {});

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

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

}

cout << endl;

return 0;

}

Answer 1

#include"stdafx.h"
#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;                            


}