Question

Write code in your “main” function that performs the following:

a) For each n є {10^3, 5x10^3, 10^4, 5x10^4, 10^5}, randomly generate 5 integer arrays of length n. b) Run each of the five comparison sorts you implemented in Step 1 on all the five arrays generated in Step 2.a and record the worst-case actual running time and number of comparisons performed among elements in the input array.

#include<iostream>
#include<cmath>

using namespace std;

void displayArray(int a[], int n)

{

cout<<"\nArray once it’s sorted: "< for(int i=0;i cout< cout<

}

void selectionSort(int a[], int n)

{

for(int i=0;i

{
int min=i;
for(int j=i+1;j if(a[min]>a[j])
min=j;
int temp=a[min];
a[min]=a[i];
a[i]=temp;
}

displayArray(a,n);   
}

void insertionSort(int a[], int n)

{

for(int i=1;i

{
int min=a[i];
int j=i-1;

while(j>=0 && a[j]>min)

{
a[j+1]=a[j];        //shifting
--j;

}
}
displayArray(a,n);
}

void shellSort(int a[], int n)

{

int k= floor(log2(n));
int gap=pow(2,k)-1;

while(gap>=1)

{

for(int i=gap;i

{
int temp=a[i];
int j;
for (j=i;j>=gap&&a[j-gap]>temp;j-=gap)
a[j]=a[j-gap];

a[j]=temp;
}

k--;
gap=pow(2,k)-1; //decrement gap

}

displayArray(a,n);
}

void swap(int* a, int* b)

{
int t=*a;
*a=*b;
*b=t;
}

int partition (int a[], int low, int high)

{
int pivot=a[high];
int i=(low-1);

for(int j=low;j<=high-1;j++)
{

if(a[j] {
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[high]);
return (i+1);
}

void quickSort(int a[], int low, int high)

{

if (low

{

int pi=partition(a, low, high);

quickSort(a, low, pi-1);
quickSort(a, pi+1, high);

}

}
void merge(int a[], int l, int m, int r)

{

int i, j, k;
int n1=m-l+1;
int n2=r-m;

int L[n1], R[n2];

for (i=0;i L[i]=a[l+i];
for (j=0;j R[j]=a[m+1+j];

i=0;
j=0;
k=l;

while(i

{

if(L[i]<=R[j])

{

a[k]=L[i];
i++;
}
else

{

a[k]=R[j];
j++;

}
    k++;

}

while(i

{

a[k]=L[i];

i++;

k++;
}

while(j

{
a[k]=R[j];
j++;
k++;
}

}

void mergeSort(int a[], int l, int r)

{

if(l

{

int m=l+(r-l)/2;

mergeSort(a, l, m);
mergeSort(a, m+1, r);

merge(a, l, m, r);
}

}

int main()

{

int n;
cout<<"Please enter the total number of elements: ";
cin>>n;
int a[n];
cout<<"Enter your elements:"< for(int i=0;i cin>>a[i];

cout<<"Pick a sorting algorith: "< cout<<"1-Selection sort"< cout<<"2-Insertion sort"< cout<<"3-Shell sort"< cout<<"4-Quick sort"< cout<<"5-Merge sort"<

int choice=0;
cout<<"Enter your choice 1 - 5: ";
cin>>choice;

switch(choice){

case 1:selectionSort(a,n);
break;
case 2:insertionSort(a,n);
break;
case 3:shellSort(a,n);
break;
case 4:quickSort(a,0,n-1);
displayArray(a,n);
break;
case 5:mergeSort(a,0,n-1);
displayArray(a,n);
break;
default:cout<<"Invalid Option"<

}

return 0;
}

Answer 1

#include<iostream>
#include<cmath>

using namespace std;

void displayArray(int a[], int n)

{

cout<<"\nArray once it’s sorted: "< for(int i=0;i cout< cout<

}

void selectionSort(int a[], int n)

{

for(int i=0;i

{
int min=i;
for(int j=i+1;j if(a[min]>a[j])
min=j;
int temp=a[min];
a[min]=a[i];
a[i]=temp;
}

displayArray(a,n);   
}

void insertionSort(int a[], int n)

{

for(int i=1;i

{
int min=a[i];
int j=i-1;

while(j>=0 && a[j]>min)

{
a[j+1]=a[j];        //shifting
--j;

}
}
displayArray(a,n);
}

void shellSort(int a[], int n)

{

int k= floor(log2(n));
int gap=pow(2,k)-1;

while(gap>=1)

{

for(int i=gap;i

{
int temp=a[i];
int j;
for (j=i;j>=gap&&a[j-gap]>temp;j-=gap)
a[j]=a[j-gap];

a[j]=temp;
}

k--;
gap=pow(2,k)-1; //decrement gap

}

displayArray(a,n);
}

void swap(int* a, int* b)

{
int t=*a;
*a=*b;
*b=t;
}

int partition (int a[], int low, int high)

{
int pivot=a[high];
int i=(low-1);

for(int j=low;j<=high-1;j++)
{

if(a[j] {
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[high]);
return (i+1);
}

void quickSort(int a[], int low, int high)

{

if (low

{

int pi=partition(a, low, high);

quickSort(a, low, pi-1);
quickSort(a, pi+1, high);

}

}
void merge(int a[], int l, int m, int r)

{

int i, j, k;
int n1=m-l+1;
int n2=r-m;

int L[n1], R[n2];

for (i=0;i L[i]=a[l+i];
for (j=0;j R[j]=a[m+1+j];

i=0;
j=0;
k=l;

while(i

{

if(L[i]<=R[j])

{

a[k]=L[i];
i++;
}
else

{

a[k]=R[j];
j++;

}
    k++;

}

while(i

{

a[k]=L[i];

i++;

k++;
}

while(j

{
a[k]=R[j];
j++;
k++;
}

}

void mergeSort(int a[], int l, int r)

{

if(l

{

int m=l+(r-l)/2;

mergeSort(a, l, m);
mergeSort(a, m+1, r);

merge(a, l, m, r);
}

}

int main()

{

int n;
cout<<"Please enter the total number of elements: ";
cin>>n;
int a[n];
cout<<"Enter your elements:"< for(int i=0;i cin>>a[i];

cout<<"Pick a sorting algorith: "< cout<<"1-Selection sort"< cout<<"2-Insertion sort"< cout<<"3-Shell sort"< cout<<"4-Quick sort"< cout<<"5-Merge sort"<

int choice=0;
cout<<"Enter your choice 1 - 5: ";
cin>>choice;

switch(choice){

case 1:selectionSort(a,n);
break;
case 2:insertionSort(a,n);
break;
case 3:shellSort(a,n);
break;
case 4:quickSort(a,0,n-1);
displayArray(a,n);
break;
case 5:mergeSort(a,0,n-1);
displayArray(a,n);
break;
default:cout<<"Invalid Option"<

}

return 0;
}