Question

DESCRIPTION

Implement a program in C++ that generates a specified number of random integers, records them in three arrays, then sorts the arrays with Insertion Sort, Merge Sort, and Quick Sort, respectively. Augment the three sorting algorithms with counters and report the number of characteristic operations each performs in sorting the (same) random values.

INPUT

The program reads from the terminal the number of random integers to generate, a seed value for the pseudo-random number generator, and a character that indicates whether or not to print the unsorted and sorted values.

OUTPUT

The program reports to the terminal the numbers of executions of characteristic operations performed by each sorting algorithm and, at the user's discretion, the unsorted and sorted values themselves.

ERRORS

The program can assume that its input is as described; it need not detect any errors.

EXAMPLE

A run of the program might look like this:

      Enter the number of values to generate and sort, between 1 and 5000: 750
      Enter an integer seed value: 42
      Print the values? n

      Insertion Sort count = 145364
      Merge Sort count = 14452
      Quick Sort count = 7785
    

Your mileage almost certainly will vary.

PLEASE HELP!!

Use the program to observe how the algorithms' times, as represented by the counts of characteristic operations, increase as the number n of values being sorted grows, by running the program on several instances of several problem sizes; that is, numbers of values to sort. Do the results confirm our discussions of the algorithms' big-O times in class? Consider graphs of operation counts against problem size. Do the numbers of operations vary with the initial arrangement of the values?

Answer 1

#include<iostream>
#include<stdlib.h>
using namespace std;
static int mergecount;
static int quickcount;
int insert_algo(int *arr1, int n)
{
int i,v,j,op=0;
for (int i = 0; i < n; i++)
{
op+=2;//for condition and i value
v = arr1[i];op+=2;//assignment
j = i - 1;
while (v < arr1[j] && j >= 0)
{op+=2;//2 conditions
// For descending order, change key<array[j] to key>array[j].
arr1[j + 1] = arr1[j];op+=2;//for j+1 and assignment
--j;op++;
}
arr1[j + 1] = v;op+=2;//for j+1 and assignment
}cout<<"\nOperations Count for Insertion sort is:"<<op<<" \n";
}
void merg(int *arr2, int l, int m, int h)
{
/* Create L ← arr2[l..m] and M ← arr2[m+1..r] */
int n1 = m - l + 1,i,j,k;
int n2 = h - m;
mergecount+=2;
int L[n1], M[n2];

for (i = 0; i < n1; i++)
{
L[i] = arr2[l + i];
mergecount+=4;// 2 for i and 2 for assignment in L
}

for (j = 0; j < n2; j++)
{
M[j] = arr2[m + 1 + j];
mergecount+=4;
}

/* Maintain current index of sub-arrays and main array */
i = 0;
j = 0;
k = l;
mergecount+=2;

/* Until we reach either end of either L or M, pick larger among elements L and M and place them in the correct position at arr2[l..h] */
while (i < n1 && j < n2)
{mergecount+=2;
if (L[i] <= M[j])
{
arr2[k] = L[i];
i++;
mergecount+=3;
}
else
{
arr2[k] = M[j];
j++;
mergecount+=2;
}
k++;
mergecount+=1;
}

/* When we run out of elements in either L or M, pick up the remaining elements and put in arr2[l..h] */
while (i < n1)
{
arr2[k] = L[i];
i++;
k++;
mergecount+=4;
}

while (j < n2)
{
arr2[k] = M[j];
j++;
k++;
mergecount+=4;
}
}

void merge_algo(int *arr2,int l,int h) {
int m;

if(l < h) {mergecount++;
m = (l + h) / 2;mergecount+=2;//assignment and calculation
merge_algo(arr2,l, m);mergecount;
merge_algo(arr2,m+1, h);mergecount;
merg(arr2,l, m, h);mergecount;
} else {
return;
}
}

int partition(int *arr3, int low, int high)
{
int pivot = arr3[high];
int i = (low - 1),j,t;
quickcount+=2;
for (int j = low; j < high; j++)
{quickcount+=2;
if (arr3[j] <= pivot)
{
i++;
t=arr3[i];
arr3[i]=arr3[j];
arr3[j]=t;
quickcount+=5;
}
}
t=arr3[i+1];
arr3[i+1]=arr3[high];
arr3[high]=t;
quickcount+=4;
return (i + 1);
}
void quick_algo(int *arr3, int low, int high)
{
int pi;
if (low < high)
{
pi = partition(arr3, low, high);
quick_algo(arr3, low, pi - 1);
quick_algo(arr3, pi + 1, high);
quickcount+=4;
}
}

int main(){
int n,seed,i,num,*inp, *arr1,*arr2,*arr3;char c;
cout<<"Enter number of values between range 1 and 10000: ";cin>>n;
inp = new int[n];
arr1 = new int[n];
arr2 = new int[n];
arr3 = new int[n];
cout<<"Enter seed integer: ";cin>>seed;
cout<<"Print the values? 'Y' or 'N' ";cin>>c;
srand(seed);
for(i=0;i<n;i++){
num=(rand() %10000);
inp[i]=num;arr1[i] = num;arr2[i] = num;arr3[i] = num;
}
insert_algo(arr1,n);
merge_algo(arr2,0,n-1);
cout<<"\nMerge count: "<<mergecount;

quick_algo(arr3,0,n-1);
cout<<"\nQuick count: "<<quickcount;
if(c =='y' || c =='Y'){
cout<<"\n input: ";
for(i=0;i<n;i++){
cout<<inp[i]<<" ";
}
cout<<"\n Insertion sort: ";
for(i=0;i<n;i++){
cout<<arr1[i]<<" ";
}
cout<<"\n merge sort: ";
for(i=0;i<n;i++){
cout<<arr2[i]<<" ";
}
cout<<"\n quick sort: ";
for(i=0;i<n;i++){
cout<<arr3[i]<<" ";
}

}

}

SCREEN SHOTS:

SO, IF INPUT SIZE INCREASES, QUICKSORT PERFOMING IN LESS NUMBER OF OPERATIONS CAMPARED TO INSERTION & MERGE SORTS.NEXT BEST IS MERGE SORT.