In c++, write a program to analyze the time complexities of four different sorti

Question

In c++, write a program to analyze the time complexities of four different sorting

algorithms. The program needs to:

Implement a random number generator function that can generate integer numbers be- tween 1 and 20000. Duplicate numbers should not be allowed. You can make use of any of the random number generating available in C library, or you can write your own pseudo random number generating code.

Implement algorithms for insertion sort, quick sort, heap sort, and merge sort. Given a choice between a recursive and an iterative version for a particular algorithm, you may choose either one.

Execute each sorting algorithm for the following different values of n, where nis the size of the list to be sorted,

n = 100, 500, 1000, 2000, 5000, 8000,10000.

In each case, the list consists of random numbers generated in step 1. For a particular value of n, the same input data (i.e., list to be sorted) should be given to all the sorting algorithms.

For each value of n, and for each sorting algorithm, obtain the actual execution time of the algorithm for the machine you are using for the cases when

a) an unsorted list is presented as the input data, and b) a sorted list is presented as the input data

5)when you generate the pseudo-random numbers, for n=100, please output the numbers to a text file

Explanation / Answer

Complete Program:

#include <iostream>
#include <ctime>
using namespace std;

void sortRandomIntegers(int size);
void fillRandomArray(int *items, int size);
void printArray(int *items, int size);
void copyArray(int *sour, int sstart, int size, int *dest, int dstart, int n);
void insertionSort(int *items, int size);
void mergeSort(int *items, int size);
void merge(int *temp1, int *temp2, int *items, int p, int q, int size);
void quickSort(int *items, int size);
void quickSort(int *items, int l, int r);
int partition(int *items, int l, int r);
void heapSort(int *items, int size);
void constructHeap(int *items, int size);
void deleteMax(int *items, int size);

int main()
{
srand(time(NULL));

sortRandomIntegers(100);
sortRandomIntegers(500);
sortRandomIntegers(1000);
sortRandomIntegers(2000);
sortRandomIntegers(5000);
sortRandomIntegers(8000);
sortRandomIntegers(10000);

system("pause");
return 0;
}

void sortRandomIntegers(int size)
{
cout << " Elapsed time in clicks for " << size << " random integers: " << endl;

clock_t start, end, elapsed;
int *t1 = new int[size];
int *t2 = new int[size];
int *t3 = new int[size];
int *t4 = new int[size];
      
int *arr = new int[size];  
fillRandomArray(arr, size);
  
copyArray(arr, 0, size, t1, 0, size);
copyArray(arr, 0, size, t2, 0, size);
copyArray(arr, 0, size, t3, 0, size);
copyArray(arr, 0, size, t4, 0, size);
  
start = 0; end = 0; elapsed = 0;  
start = clock();
insertionSort(t1, size); // insertion sort
end = clock();  
elapsed = end - start;  
cout << "Insertion Sort: " << elapsed << endl;
    
start = 0; end = 0; elapsed = 0;  
start = clock();
mergeSort(t2, size); // merge sort
end = clock();  
elapsed = end - start;  
cout << "Merge Sort: " << elapsed << endl;
  
start = 0; end = 0; elapsed = 0;  
start = clock();
quickSort(t3, size); // quick sort
end = clock();  
elapsed = end - start;  
cout << "Quick Sort: " << elapsed << endl;
  
start = 0; end = 0; elapsed = 0;  
start = clock();
heapSort(t4, size); // heap sort
end = clock();  
elapsed = end - start;  
cout << "Heap Sort: " << elapsed << endl;
}

void fillRandomArray(int *items, int size)
{
// random numbers between 1-20000
for(int i = 0; i < size; i++)
{
  items[i] = 1 + rand() % 10;
}
}

void printArray(int *items, int size)
{
for(int i = 0; i < size; i++)
{
  cout << items[i] << " ";
}
cout << endl;
}

void copyArray(int *sour, int sstart, int size, int *dest, int dstart, int n)
{
for(int i = sstart, j = dstart; i < size; i++, j++)
{
  dest[j] = sour[i];
}
}

void insertionSort(int *items, int size)
{
for(int i = 1; i < size; i++)
{
  int temp = items[i];
  int j = i;

  while(j > 0 && temp < items[j - 1])
  {
   items[j] = items[j - 1];
   j--;
  }

  items[j] = temp;
}
}

void mergeSort(int *items, int size)
{
int s1 = size / 2;
int s2 = size - s1;
int *temp1 = new int[s1];
int *temp2 = new int[s2];

if(size > 1)
{
  copyArray(items, 0, size, temp1, 0, s1);
  copyArray(items, s1, size, temp2, 0, s2);

  mergeSort(temp1, s1);
  mergeSort(temp2, s2);
  merge(temp1, temp2, items, s1, s2, size);
}
}

void merge(int *temp1, int *temp2, int *items, int p, int q, int size)
{
int i = 0;
int j = 0;
int k = 0;

while(i < p && j < q)
{
  if(temp1[i] <= temp2[j])
  {
   items[k] = temp1[i];
   i = i + 1;
  }
  else
  {
   items[k] = temp2[j];
   j = j + 1;
  }

  k = k + 1;
}

if(i == p)
  copyArray(temp2, j, size, items, k, q - j);
else
  copyArray(temp1, i, size, items, k, p - i);
}

void quickSort(int *items, int size)
{
quickSort(items, 0, size - 1);
}

void quickSort(int *items, int l, int r)
{
int s = partition(items, l, r);

if(l < s - 1)
  quickSort(items, l, s - 1);
if(s < r)
  quickSort(items, s, r);
}

int partition(int *items, int l, int r)
{
int p = l;
int q = r;
int temp;
int pivot;
pivot = items[(l + r) / 2];

while(p <= q)
{
  while(items[p] < pivot)
   p++;
  while(items[q] > pivot)
   q--;

  if(p <= q)
  {
   temp = items[p];
   items[p] = items[q];
   items[q] = temp;
   p++;
   q--;
  }
}
return p;
}

void heapSort(int *items, int size)
{
constructHeap(items, size);
deleteMax(items, size);
}
  
void constructHeap(int *items, int size)
{  
int j, k, temp;
for(int i = 1; i < size; i++)
{
  j = i;
   
  do
  {
   k = (j - 1) / 2;    
   if(items[k] < items[j])
   {
    temp = items[k];
    items[k] = items[j];
    items[j] = temp;
   }
    
   j = k;
    
  } while(k != 0);   
}  
}

void deleteMax(int *items, int size)
{
for(int i = size - 1; i > 0; i--)
{   
  int temp = items[0];
  items[0] = items[i];
  items[i] = temp;
   
  constructHeap(items, i);
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.