Answer:
header.h->function bodies and header files.
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
/* Partitioning the array on the basis of piv value. */
int Partition(int a[], int bot, int top,string opt)
{
int piv, ind=bot, i, swp;
/*Finding the piv value according to string opt*/
if(opt=="Type1 sort" || opt=="Type3 sort")
{
piv=(top+bot)/2;
}
else if(opt=="Type2 sort" || opt=="Type4 sort")
{
piv=(top+bot)/2;
if((a[top]>=a[piv] && a[top]<=a[bot]) || (a[top]>=a[bot] && a[top]<=a[piv]))
piv=top;
else if((a[bot]>=a[piv] && a[bot]<=a[top]) || (a[bot]>=a[top] && a[bot]<=a[piv]))
piv=bot;
}
swp=a[piv];
a[piv]=a[top];
a[top]=swp;
piv=top;
/*Getting ind of the piv.*/
for(i=bot; i < top; i++)
{
if(a[i] < a[piv])
{
swp=a[i];
a[i]=a[ind];
a[ind]=swp;
ind++;
}
}
swp=a[piv];
a[piv]=a[ind];
a[ind]=swp;
return ind;
}
void QuickSort(int a[], int bot, int top, string opt)
{
int pindex;
if((opt=="Type3 sort" || opt=="Type4 sort") && top-bot<19)
{
/*then insertion sort*/
int swp,ind;
for(int i=bot+1;i<=top;i++){
swp=a[i];
ind=i;
for(int j=i-1;j>=bot;j--){
if(swp<a[j]){
a[j+1]=a[j];
ind=j;
}
else
break;
}
a[ind]=swp;
}
}
else if(bot < top)
{
/* Partitioning the array*/
pindex =Partition(a, bot, top,opt);
/* Recursively implementing QuickSort.*/
QuickSort(a, bot, pindex-1,opt);
QuickSort(a, pindex+1, top,opt);
}
return ;
}
main.cpp->main driver file
#include "header.h"
int main()
{
int n=100000, i;
/*creating randomized array of 100000 numbers between 0 and 100001*/
int arr[n];
int b[n];
for(i = 0; i < n; i++)
arr[i]=(rand() % 100000) + 1;
clock_t t1,t2;
t1=clock();
QuickSort(arr, 0, n-1,"Type1 sort");
t2=clock();
for( i=0;i<n;i++)
arr[i]=b[i];
cout<<"Quick sort time, with pivot middle element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );
cout<<"\n";
t1=clock();
QuickSort(arr, 0, n-1,"Type2 sort");
t2=clock();
for( i=0;i<n;i++)
arr[i]=b[i];
cout<<"Quick sort time, with pivot median element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );
cout<<"\n";
t1=clock();
QuickSort(arr, 0, n-1,"Type3 sort");
t2=clock();
for( i=0;i<n;i++)
arr[i]=b[i];
cout<<"Quick sort time and insertion sort time, with pivot middle element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );
cout<<"\n";
t1=clock();
QuickSort(arr, 0, n-1,"Type4 sort");
t2=clock();
cout<<"Quick sort time and insertion sort time, with pivot median element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );
return 0;
}
Explanation:
Change the value of n in the main file for different array size. Output is in the same format as mentioned, time is shown in milliseconds.
