An Interesting Analysis on the variation of time on different Sorting algorithms.

Hello everyone,

My name is Taha khan. Currently, I am doing bachelor in Computer Science from FAST-NUCES , Karachi and I am a second year student.

“HOW TIME COMPLEXITY VARIES ON DIFFERENT SORTING ALGORITHMS WITH DISTINCTIVE SIZE(total no of elements)”.

In our daily life, we are witnessing ample of applications which makes our hectic and burdensome tasks , easy by doing these in a while. These applications has significant importance in real world because they saves our important time For instance ; calculator and computer. Therefore, How speedily these applications executes our assigned task is very crucial. We don’t want our applications to take so long that they get bogged down and slow. Hence; The purpose of this article regulating around which sorting algorithms consumes less time on different size of data set so we can make better choice and applications more steadfast.

Here I am considering following Algorithms.

  • Merge sort.
  • Quick sort I ( Middle number as pivot).
  • Quick sort II( Random number as pivot).
  • Quick sort III ( Median as pivot).
  • Quick sort IV( Median updated as pivot).

Explanation:

I took seven integer data sets of following sizes.

  • With 100 Elements.
  • With 200 Elements.
  • With 300 Elements.
  • With 400 Elements.
  • With 500 Elements.
  • With 1000 Elements.

Firstly, Integers data in each data set has been randomly generated and each data set has been stored in seperate .txt file. After this, we applied all aforesaid sorting algorithms on individual data set.

First, we applied insertion sort which is a best choice for less numbers of elements.

Then, we applied merge sort which is preferred for large data . It is far better than insertion sort because its time complexity is 0(N log N) where as insertion sort has time complexity 0(N²).

After this we applied quick sorts . As the main funda in quick sort is the selection of pivot element. Therefore we select multiple pivot elements and then note down the compilation time.

Firstly we applied Quick sort I in which we choose middle element as the pivot and then we sort our list with respect to this pivot element.

Secondly we note down the compilation time of quick sort II , in which we select the random element as pivot.

Thirdly ,we sorted our array by choosing the median of first , middle and last element.

Lastly we make our quick sort stable by choosing median updated as pivot and applying sorting.

One can understand the above details by interpreting the following graphs .

Graphs:

Graph has been generated by note down the average reading of compilition time for each sorting algorithms.

Analysis of graphs:

Insertion sort:

Insertion sort takes 1.17 seconds for sorting 50 elements and 1.45 seconds for sorting 1000 elements. We can conclude from the graphs that time taken by insertion sort is continuously increasing. Hence, it proved that it is best for less number of elements.

Merge sort:

Merge sort works faster than insertion sort when we have larger size of data.

Hence in these cases, the plotting point of insertion is above than merge sort.

Quick sorts:

As we can see from the graphs that all types of quick sorts depicts inconsistent result. The question is that why so?

The reason is that quick sort is only dependent on selection of pivot and every time pivot selection is getting changed. Therefore we should choose our pivot wisely so that we cannot fall into the worst case.

Time complexity of sorting algorithms:

In Merge Sort the Worst Case: O(N*log N), Average Case: O(N*log N), and Best Case: O(N*log N),
whereas
In Insertion Sort the Worst Case: O(N2), Average Case: O(N2), and Best Case: O(N).

In quick sort worst case time complexity is 0(N²).

Codes:

FOR 50 ELEMENTS:

//CODE FOR 50 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
void insertionsort(int array[], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && array[j]>temp)
{
array[j+1]=array[j];
j — ;
}
array[j+1]=temp;
}
for(i=0;i<n;i++)
{
cout<<” “<<array[i];
}}

void Merge(int array[], int l, int h, int mid)
{
int i, j, k, temp[h-l+1];
i = l;
k = 0;
j = mid+1;

while (i <= mid && j <= h)
{
if (array[i] < array[j])
{
temp[k] = array[i];
k++;
i++;
}
else
{
temp[k] = array[j];
k++;
j++;
}
}

while (i <= mid)
{
temp[k] = array[i];
k++;
i++;
}

while (j <= h)
{
temp[k] = array[j];
k++;
j++;
}

for (i = l; i <= h; i++)
{
array[i] = temp[i-l];
}
}

//merge sort
void Merge_sort(int array[], int l, int h)
{
int mid;
if (l < h)
{
mid=(l+h)/2;
Merge_sort(array, l, mid);
Merge_sort(array, mid+1, h);
Merge(array, l, h, mid);
}
}
////
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
void quick_sort1(int array[], int left, int right)
{
int l, r, n=right+1;
int pivot;

if(left >= right)
return ;
else
{

l = left;
r = right;

int mid=(left + right) /2;
pivot = array[mid];

while(l <= r) {
while(array[l] < pivot)
{
l++;
}
while(array[r] > pivot)
{
r — ;
}
if(l <= r) {
swap(&array[l],&array[r]);
l++;
r — ;
}
}

quick_sort1(array,left,r);
quick_sort1(array,l,right);
}
}

int quicksort2_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}

swap(&array[ind + 1], &array[high]);
return (ind + 1);
}

int random(int array[], int low, int high) {
int pivot;
int r = rand();
pivot = low + r% (high — low + 1); // Randomizing the pivot
return quicksort2_partition(array, low, high);
}
//
//
void quickSort2(int array[], int low, int high) {
if (low < high) {
int n= random(array, low, high);

quickSort2(array, low, n — 1);
quickSort2(array, n + 1, high);
} }

int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
int median(int array[], int low, int high) {

int pivot;
int mid = (high+low) / 2;
if (array[mid] < array[low])
{
swap(&array[mid], &array[low]);
}

if (array[high] < array[low])
{
swap(&array[high], &array[low]);}
if (array[high] < array[mid])
{
swap(&array[high], &array[mid]);}

swap(&array[mid], &array[high-1]);

pivot = array[high-1];

return quicksort3_partition(array, low, high);
}

//
void quickSort3(int array[], int low, int high) {
if (low < high) {
int n= median(array, low, high);

quickSort3(array, low, n — 1);
quickSort3(array, n + 1, high);
}
}




void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

// clock_t start, end;
// start = clock();
fstream obj;
int n=50;
int array[n];
obj.open(“50_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
insertionsort(array,n);
Merge_sort(array, 0, n-1);
quick_sort1(array, 0, n-1);
quickSort2(array,0,n-1);
quickSort3(array,0,n-1);
//quicksort4(array,0,n-1);
// end = clock( );
// double time_taken = double(end — start) / double (CLOCKS_PER_SEC);
// cout<<” Time Taken: “<<setprecision(5)<<time_taken<<” seconds.”;
// Merge_sort(array, 0, n-1);
// quick_sort1(array, 0, n-1);
// quickSort2(array,0,n-1);
//quickSort3(array,0,n-1);
// quicksort4(array,0,n-1);


obj.close();
}

FOR 100 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
//void insertionsort(int array[], int n)
//{
// int i,j,temp;
// for(i=1;i<n;i++)
// {
// temp=array[i];
// j=i-1;
// while(j>=0 && array[j]>temp)
// {
// array[j+1]=array[j];
// j — ;
// }
// array[j+1]=temp;
// }
//// for(i=0;i<n;i++)
//// {
//// cout<<” “<<array[i];
//// }
//}

//void Merge(int array[], int l, int h, int mid)
//{
// int i, j, k, temp[h-l+1];
// i = l;
// k = 0;
// j = mid+1;
//
// while (i <= mid && j <= h)
// {
// if (array[i] < array[j])
// {
// temp[k] = array[i];
// k++;
// i++;
// }
// else
// {
// temp[k] = array[j];
// k++;
// j++;
// }
// }
//
// while (i <= mid)
// {
// temp[k] = array[i];
// k++;
// i++;
// }
//
// while (j <= h)
// {
// temp[k] = array[j];
// k++;
// j++;
// }
//
// for (i = l; i <= h; i++)
// {
// array[i] = temp[i-l];
// }
//}
//
// //merge sort
//void Merge_sort(int array[], int l, int h)
//{
// int mid;
// if (l < h)
// {
// mid=(l+h)/2;
// Merge_sort(array, l, mid);
// Merge_sort(array, mid+1, h);
// Merge(array, l, h, mid);
// }
//}
//
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
// void quick_sort1(int array[], int left, int right)
//{
// int l, r, n=right+1;
// int pivot;
//
// if(left >= right)
// return ;
// else
// {
//
// l = left;
// r = right;
//
// int mid=(left + right) /2;
// pivot = array[mid];
//
// while(l <= r) {
// while(array[l] < pivot)
// {
// l++;
// }
// while(array[r] > pivot)
// {
// r — ;
// }
// if(l <= r) {
// swap(&array[l],&array[r]);
// l++;
// r — ;
// }
// }
//
// quick_sort1(array,left,r);
// quick_sort1(array,l,right);
//}
//}
//
//
// int quicksort2_partition(int array[], int low, int high) {
// int pivot = array[high];
// int ind = (low — 1);
//
// for (int j = low; j < high; j++) {
// if (array[j] < pivot) {
// swap(&array[++ind], &array[j]);
// }
// }
//
// swap(&array[ind + 1], &array[high]);
// return (ind + 1);
//}
//
//
//
//
// int random(int array[], int low, int high) {
// int pivot;
// int r = rand();
// pivot = low + r% (high — low + 1); // Randomizing the pivot
// return quicksort2_partition(array, low, high);
//}
//
//
// void quickSort2(int array[], int low, int high) {
// if (low < high) {
// int n= random(array, low, high);
//
// quickSort2(array, low, n — 1);
// quickSort2(array, n + 1, high);
// } }
//
int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
// int median(int array[], int low, int high) {
//
// int pivot;
// int mid = (high+low) / 2;
// if (array[mid] < array[low])
// {
// swap(&array[mid], &array[low]);
// }
//
// if (array[high] < array[low])
// {
// swap(&array[high], &array[low]);}
// if (array[high] < array[mid])
// {
// swap(&array[high], &array[mid]);}
//
// swap(&array[mid], &array[high-1]);
//
// pivot = array[high-1];
//
// return quicksort3_partition(array, low, high);
//}
//
////
// void quickSort3(int array[], int low, int high) {
// if (low < high) {
// int n= median(array, low, high);
//
// quickSort3(array, low, n — 1);
// quickSort3(array, n + 1, high);
// }
// }
//
//
//
//
void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

fstream obj;
int n=100;
int array[n];
obj.open(“100_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
//insertionsort(array,n);
//Merge_sort(array, 0, n-1);
// quick_sort1(array, 0, n-1);
//quickSort2(array,0,n-1);
//quickSort3(array,0,n-1);
quicksort4(array,0,n-1);


obj.close();
}

FOR 200 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
void insertionsort(int array[], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && array[j]>temp)
{
array[j+1]=array[j];
j — ;
}
array[j+1]=temp;
}
// for(i=0;i<n;i++)
// {
// cout<<” “<<array[i];
// }
}
//
//
void Merge(int array[], int l, int h, int mid)
{
int i, j, k, temp[h-l+1];
i = l;
k = 0;
j = mid+1;

while (i <= mid && j <= h)
{
if (array[i] < array[j])
{
temp[k] = array[i];
k++;
i++;
}
else
{
temp[k] = array[j];
k++;
j++;
}
}

while (i <= mid)
{
temp[k] = array[i];
k++;
i++;
}

while (j <= h)
{
temp[k] = array[j];
k++;
j++;
}

for (i = l; i <= h; i++)
{
array[i] = temp[i-l];
}
}
//
// //merge sort
void Merge_sort(int array[], int l, int h)
{
int mid;
if (l < h)
{
mid=(l+h)/2;
Merge_sort(array, l, mid);
Merge_sort(array, mid+1, h);
Merge(array, l, h, mid);
}
}
//
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
void quick_sort1(int array[], int left, int right)
{
int l, r, n=right+1;
int pivot;

if(left >= right)
return ;
else
{

l = left;
r = right;

int mid=(left + right) /2;
pivot = array[mid];

while(l <= r) {
while(array[l] < pivot)
{
l++;
}
while(array[r] > pivot)
{
r — ;
}
if(l <= r) {
swap(&array[l],&array[r]);
l++;
r — ;
}
}

quick_sort1(array,left,r);
quick_sort1(array,l,right);
}
}

int quicksort2_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}

swap(&array[ind + 1], &array[high]);
return (ind + 1);
}

int random(int array[], int low, int high) {
int pivot;
int r = rand();
pivot = low + r% (high — low + 1); // Randomizing the pivot
return quicksort2_partition(array, low, high);
}


void quickSort2(int array[], int low, int high) {
if (low < high) {
int n= random(array, low, high);

quickSort2(array, low, n — 1);
quickSort2(array, n + 1, high);
} }
//
int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
int median(int array[], int low, int high) {

int pivot;
int mid = (high+low) / 2;
if (array[mid] < array[low])
{
swap(&array[mid], &array[low]);
}

if (array[high] < array[low])
{
swap(&array[high], &array[low]);}
if (array[high] < array[mid])
{
swap(&array[high], &array[mid]);}

swap(&array[mid], &array[high-1]);

pivot = array[high-1];

return quicksort3_partition(array, low, high);
}

//
void quickSort3(int array[], int low, int high) {
if (low < high) {
int n= median(array, low, high);

quickSort3(array, low, n — 1);
quickSort3(array, n + 1, high);
}
}




void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

fstream obj;
int n=200;
int array[n];
obj.open(“200_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
//insertionsort(array,n);
//Merge_sort(array, 0, n-1);
// quick_sort1(array, 0, n-1);
//quickSort2(array,0,n-1);
// quickSort3(array,0,n-1);
quicksort4(array,0,n-1);


obj.close();
}

FOR 300 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
void insertionsort(int array[], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && array[j]>temp)
{
array[j+1]=array[j];
j — ;
}
array[j+1]=temp;
}
// for(i=0;i<n;i++)
// {
// cout<<” “<<array[i];
// }
}
//
//
void Merge(int array[], int l, int h, int mid)
{
int i, j, k, temp[h-l+1];
i = l;
k = 0;
j = mid+1;

while (i <= mid && j <= h)
{
if (array[i] < array[j])
{
temp[k] = array[i];
k++;
i++;
}
else
{
temp[k] = array[j];
k++;
j++;
}
}

while (i <= mid)
{
temp[k] = array[i];
k++;
i++;
}

while (j <= h)
{
temp[k] = array[j];
k++;
j++;
}

for (i = l; i <= h; i++)
{
array[i] = temp[i-l];
}
}
//
// //merge sort
void Merge_sort(int array[], int l, int h)
{
int mid;
if (l < h)
{
mid=(l+h)/2;
Merge_sort(array, l, mid);
Merge_sort(array, mid+1, h);
Merge(array, l, h, mid);
}
}
//
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
void quick_sort1(int array[], int left, int right)
{
int l, r, n=right+1;
int pivot;

if(left >= right)
return ;
else
{

l = left;
r = right;

int mid=(left + right) /2;
pivot = array[mid];

while(l <= r) {
while(array[l] < pivot)
{
l++;
}
while(array[r] > pivot)
{
r — ;
}
if(l <= r) {
swap(&array[l],&array[r]);
l++;
r — ;
}
}

quick_sort1(array,left,r);
quick_sort1(array,l,right);
}
}

int quicksort2_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}

swap(&array[ind + 1], &array[high]);
return (ind + 1);
}

int random(int array[], int low, int high) {
int pivot;
int r = rand();
pivot = low + r% (high — low + 1); // Randomizing the pivot
return quicksort2_partition(array, low, high);
}


void quickSort2(int array[], int low, int high) {
if (low < high) {
int n= random(array, low, high);

quickSort2(array, low, n — 1);
quickSort2(array, n + 1, high);
} }
//
int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
int median(int array[], int low, int high) {

int pivot;
int mid = (high+low) / 2;
if (array[mid] < array[low])
{
swap(&array[mid], &array[low]);
}

if (array[high] < array[low])
{
swap(&array[high], &array[low]);}
if (array[high] < array[mid])
{
swap(&array[high], &array[mid]);}

swap(&array[mid], &array[high-1]);

pivot = array[high-1];

return quicksort3_partition(array, low, high);
}

//
void quickSort3(int array[], int low, int high) {
if (low < high) {
int n= median(array, low, high);

quickSort3(array, low, n — 1);
quickSort3(array, n + 1, high);
}
}




void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

fstream obj;
int n=300;
int array[n];
obj.open(“300_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
//insertionsort(array,n);
//Merge_sort(array, 0, n-1);
// quick_sort1(array, 0, n-1);
// quickSort2(array,0,n-1);
// quickSort3(array,0,n-1);
quicksort4(array,0,n-1);
obj.close();
}

FOR 400 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
void insertionsort(int array[], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && array[j]>temp)
{
array[j+1]=array[j];
j — ;
}
array[j+1]=temp;
}
// for(i=0;i<n;i++)
// {
// cout<<” “<<array[i];
// }
}
//
//
void Merge(int array[], int l, int h, int mid)
{
int i, j, k, temp[h-l+1];
i = l;
k = 0;
j = mid+1;

while (i <= mid && j <= h)
{
if (array[i] < array[j])
{
temp[k] = array[i];
k++;
i++;
}
else
{
temp[k] = array[j];
k++;
j++;
}
}

while (i <= mid)
{
temp[k] = array[i];
k++;
i++;
}

while (j <= h)
{
temp[k] = array[j];
k++;
j++;
}

for (i = l; i <= h; i++)
{
array[i] = temp[i-l];
}
}
//
// //merge sort
void Merge_sort(int array[], int l, int h)
{
int mid;
if (l < h)
{
mid=(l+h)/2;
Merge_sort(array, l, mid);
Merge_sort(array, mid+1, h);
Merge(array, l, h, mid);
}
}
//
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
void quick_sort1(int array[], int left, int right)
{
int l, r, n=right+1;
int pivot;

if(left >= right)
return ;
else
{

l = left;
r = right;

int mid=(left + right) /2;
pivot = array[mid];

while(l <= r) {
while(array[l] < pivot)
{
l++;
}
while(array[r] > pivot)
{
r — ;
}
if(l <= r) {
swap(&array[l],&array[r]);
l++;
r — ;
}
}

quick_sort1(array,left,r);
quick_sort1(array,l,right);
}
}

int quicksort2_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}

swap(&array[ind + 1], &array[high]);
return (ind + 1);
}

int random(int array[], int low, int high) {
int pivot;
int r = rand();
pivot = low + r% (high — low + 1); // Randomizing the pivot
return quicksort2_partition(array, low, high);
}


void quickSort2(int array[], int low, int high) {
if (low < high) {
int n= random(array, low, high);

quickSort2(array, low, n — 1);
quickSort2(array, n + 1, high);
} }
//
int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
int median(int array[], int low, int high) {

int pivot;
int mid = (high+low) / 2;
if (array[mid] < array[low])
{
swap(&array[mid], &array[low]);
}

if (array[high] < array[low])
{
swap(&array[high], &array[low]);}
if (array[high] < array[mid])
{
swap(&array[high], &array[mid]);}

swap(&array[mid], &array[high-1]);

pivot = array[high-1];

return quicksort3_partition(array, low, high);
}

//
void quickSort3(int array[], int low, int high) {
if (low < high) {
int n= median(array, low, high);

quickSort3(array, low, n — 1);
quickSort3(array, n + 1, high);
}
}




void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

fstream obj;
int n=400;
int array[n];
obj.open(“400_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
insertionsort(array,n);
//Merge_sort(array, 0, n-1);
// quick_sort1(array, 0, n-1);
//quickSort2(array,0,n-1);
//quickSort3(array,0,n-1);
// quicksort4(array,0,n-1);


obj.close();
}

FOR 500 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
void insertionsort(int array[], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && array[j]>temp)
{
array[j+1]=array[j];
j — ;
}
array[j+1]=temp;
}
// for(i=0;i<n;i++)
// {
// cout<<” “<<array[i];
// }
}
//
//
void Merge(int array[], int l, int h, int mid)
{
int i, j, k, temp[h-l+1];
i = l;
k = 0;
j = mid+1;

while (i <= mid && j <= h)
{
if (array[i] < array[j])
{
temp[k] = array[i];
k++;
i++;
}
else
{
temp[k] = array[j];
k++;
j++;
}
}

while (i <= mid)
{
temp[k] = array[i];
k++;
i++;
}

while (j <= h)
{
temp[k] = array[j];
k++;
j++;
}

for (i = l; i <= h; i++)
{
array[i] = temp[i-l];
}
}
//
// //merge sort
void Merge_sort(int array[], int l, int h)
{
int mid;
if (l < h)
{
mid=(l+h)/2;
Merge_sort(array, l, mid);
Merge_sort(array, mid+1, h);
Merge(array, l, h, mid);
}
}
//
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
void quick_sort1(int array[], int left, int right)
{
int l, r, n=right+1;
int pivot;

if(left >= right)
return ;
else
{

l = left;
r = right;

int mid=(left + right) /2;
pivot = array[mid];

while(l <= r) {
while(array[l] < pivot)
{
l++;
}
while(array[r] > pivot)
{
r — ;
}
if(l <= r) {
swap(&array[l],&array[r]);
l++;
r — ;
}
}

quick_sort1(array,left,r);
quick_sort1(array,l,right);
}
}

int quicksort2_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}

swap(&array[ind + 1], &array[high]);
return (ind + 1);
}

int random(int array[], int low, int high) {
int pivot;
int r = rand();
pivot = low + r% (high — low + 1); // Randomizing the pivot
return quicksort2_partition(array, low, high);
}


void quickSort2(int array[], int low, int high) {
if (low < high) {
int n= random(array, low, high);

quickSort2(array, low, n — 1);
quickSort2(array, n + 1, high);
} }
//
int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
int median(int array[], int low, int high) {

int pivot;
int mid = (high+low) / 2;
if (array[mid] < array[low])
{
swap(&array[mid], &array[low]);
}

if (array[high] < array[low])
{
swap(&array[high], &array[low]);}
if (array[high] < array[mid])
{
swap(&array[high], &array[mid]);}

swap(&array[mid], &array[high-1]);

pivot = array[high-1];

return quicksort3_partition(array, low, high);
}

//
void quickSort3(int array[], int low, int high) {
if (low < high) {
int n= median(array, low, high);

quickSort3(array, low, n — 1);
quickSort3(array, n + 1, high);
}
}




void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

fstream obj;
int n=500;
int array[n];
obj.open(“500_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
//insertionsort(array,n);
//Merge_sort(array, 0, n-1);
//quick_sort1(array, 0, n-1);
//quickSort2(array,0,n-1);
//quickSort3(array,0,n-1);
quicksort4(array,0,n-1);


obj.close();
}

FOR 1000 ELEMENTS:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<string>
using namespace std;
void insertionsort(int array[], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && array[j]>temp)
{
array[j+1]=array[j];
j — ;
}
array[j+1]=temp;
}
// for(i=0;i<n;i++)
// {
// cout<<” “<<array[i];
// }
}
//
//
void Merge(int array[], int l, int h, int mid)
{
int i, j, k, temp[h-l+1];
i = l;
k = 0;
j = mid+1;

while (i <= mid && j <= h)
{
if (array[i] < array[j])
{
temp[k] = array[i];
k++;
i++;
}
else
{
temp[k] = array[j];
k++;
j++;
}
}

while (i <= mid)
{
temp[k] = array[i];
k++;
i++;
}

while (j <= h)
{
temp[k] = array[j];
k++;
j++;
}

for (i = l; i <= h; i++)
{
array[i] = temp[i-l];
}
}
//
// //merge sort
void Merge_sort(int array[], int l, int h)
{
int mid;
if (l < h)
{
mid=(l+h)/2;
Merge_sort(array, l, mid);
Merge_sort(array, mid+1, h);
Merge(array, l, h, mid);
}
}
//
////
//void printarray(int arr[],int n)
//{
// for(int i=0;i<n;i++)
// {
// cout<<” “<<arr[i];
// }
//}
//
//
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
//
void quick_sort1(int array[], int left, int right)
{
int l, r, n=right+1;
int pivot;

if(left >= right)
return ;
else
{

l = left;
r = right;

int mid=(left + right) /2;
pivot = array[mid];

while(l <= r) {
while(array[l] < pivot)
{
l++;
}
while(array[r] > pivot)
{
r — ;
}
if(l <= r) {
swap(&array[l],&array[r]);
l++;
r — ;
}
}

quick_sort1(array,left,r);
quick_sort1(array,l,right);
}
}

int quicksort2_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}

swap(&array[ind + 1], &array[high]);
return (ind + 1);
}

int random(int array[], int low, int high) {
int pivot;
int r = rand();
pivot = low + r% (high — low + 1); // Randomizing the pivot
return quicksort2_partition(array, low, high);
}


void quickSort2(int array[], int low, int high) {
if (low < high) {
int n= random(array, low, high);

quickSort2(array, low, n — 1);
quickSort2(array, n + 1, high);
} }
//
int quicksort3_partition(int array[], int low, int high) {
int pivot = array[high];
int ind = (low — 1);

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++ind], &array[j]);
}
}
//
swap(&array[ind + 1], &array[high]);
return (ind + 1);
}
//
//
int median(int array[], int low, int high) {

int pivot;
int mid = (high+low) / 2;
if (array[mid] < array[low])
{
swap(&array[mid], &array[low]);
}

if (array[high] < array[low])
{
swap(&array[high], &array[low]);}
if (array[high] < array[mid])
{
swap(&array[high], &array[mid]);}

swap(&array[mid], &array[high-1]);

pivot = array[high-1];

return quicksort3_partition(array, low, high);
}

//
void quickSort3(int array[], int low, int high) {
if (low < high) {
int n= median(array, low, high);

quickSort3(array, low, n — 1);
quickSort3(array, n + 1, high);
}
}




void sorting(int array[], int x, int y, int z)
{
if(array[x]>=array[z])
{
swap(&array[x],&array[z]);
}
if(array[y]>=array[x])
{
swap(&array[x],&array[y]);
}
if(array[y]>=array[z])
{
swap(&array[y],&array[z]);
}
}
//
int Median4(int x1, int x2, int x3)
{
if((x1>=x2 && x1<=x3)||(x1>=x3 && x1<=x2))
{
return x1;
}
else if((x2>=x1 && x2<=x3)||(x2>=x3 && x2<=x1))
{
return x2;
}
else
{
return x3;
}

}

void quicksort4(int array[], int low, int high)
{
int mid=(low+high)/2;
int pivot=Median4(array[low],array[mid],array[high]);

sorting(array,low,mid,high);
swap(array[mid],array[high-1]);

int index=quicksort3_partition(array,low,mid);
quicksort4(array,low,high-1);
quicksort4(array,low+1,high);
}
int main( )
{

fstream obj;
int n=1000;
int array[n];
obj.open(“1000_numbers_file.txt”,ios::out);
if(!obj)
{
cout<<”FILE NOT CREATED”<<endl;
}
else
{

for(int i=0;i<n;i++)
{
array[i]=rand();
obj<<array[i];
obj<<”\n”;
}}

cout<<”COMMENT ALL SORTING FUNCTIONS FOR WHICH YOU ARE NOT CHECKING TIME COMPLEXITY\n\n\n”;
//insertionsort(array,n);
//Merge_sort(array, 0, n-1);
//quick_sort1(array, 0, n-1);
//quickSort2(array,0,n-1);
//quickSort3(array,0,n-1);
quicksort4(array,0,n-1);


obj.close();
}

Credits:

All credits goes to Miss Anaum Qureshi for giving this research-based assignment.

Any kind of error or omission will be rectified.

Linked-In profile link:

Warm Regards

Taha khan.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store