Question

C++

Write a program that can be used to compare Insertion Sort, Merge Sort and Quick Sort.

Program must:

• Read an array size from the user, dynamically an array of that size, and fill the array with random numbers
• Sort the array with the Insertion Sort, MergeSort and QuickSort algorithms studied in class, doing a time-stamp on each sort.

Use your program to measure and record the time needed to sort random arrays of size 5000, 50000, and 500000. For each array size, obtain a printout of the time required for the sorts.

Answer 1

Please find the code below:

main.cpp

#include <iostream>
#include <stdlib.h>
#include <string>
#include <chrono>
#include <fstream>
#include <sstream>
using namespace std::chrono;
using namespace std;
//swap usign by selection sort
void swap(long *xp, long *yp)
{
   long temp = *xp;
   *xp = *yp;
   *yp = temp;
}

// Get current date/time, format is YYYY-MM-DD.HH:mm:ss
const std::string currentDateTime() {
   time_t now = time(0);
   struct tm tstruct;
   char buf[80];
   tstruct = *localtime(&now);
   // Visit http://en.cppreference.com/w/cpp/chrono/c/strftime
   // for more information about date/time format
   strftime(buf, sizeof(buf), "%Y-%m-%d.%X", &tstruct);

   return buf;
}

/* Function to sort an array using insertion sort*/
void insertionSort(long arr[], int n)
{   cout<<"Insertion sort performance "<<endl;
cout << "Start time : " << currentDateTime() <<endl;
auto start = high_resolution_clock::now();
int i, key, j;
for (i = 1; i < n; i++)
{
   key = arr[i];
   j = i-1;

   /* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
   while (j >= 0 && arr[j] > key)
   {
       arr[j+1] = arr[j];
       j = j-1;
   }

   arr[j+1] = key;
}
//check the time
cout << "End time : " << currentDateTime() <<endl;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout << "Elapse time : " << duration.count() << " microseconds" << endl;

}

void selectionSort(long arr[], int n)
{
   cout<<"Selection sort performance "<<endl;
   //clock to check time
   cout << "Start time : " << currentDateTime() <<endl;
   auto start = high_resolution_clock::now();
   int i, j, min_idx;

   // One by one move boundary of unsorted subarray
   for (i = 0; i < n-1; i++)
   {
       // Find the minimum element in unsorted array
       min_idx = i;
       for (j = i+1; j < n; j++)
           if (arr[j] > arr[min_idx])
               min_idx = j;

       // Swap the found minimum element with the first element
       swap(&arr[min_idx], &arr[i]);
   }

   cout << "End time : " << currentDateTime() <<endl;
   auto stop = high_resolution_clock::now();
   auto duration = duration_cast<microseconds>(stop - start);
   cout << "Elapse time : " << duration.count() << " microseconds" << endl;
}

int partition (long arr[], int low, int high)
{
   float pivot = arr[high]; // pivot
   int i = (low - 1); // Index of smaller element

   for (int j = low; j <= high- 1; j++)
   {
       // If current element is smaller than or
       // equal to pivot
       if (arr[j] <= pivot)
       {
           i++; // increment index of smaller element
           swap(&arr[i], &arr[j]);
       }
   }
   swap(&arr[i + 1], &arr[high]);
   return (i + 1);
}

void quickSort(long arr[], int low, int high)
{
   if (low < high)
   {
       /* pi is partitioning index, arr[p] is now
at right place */
       int pi = partition(arr, low, high);

       // Separately sort elements before
       // partition and after partition
       quickSort(arr, low, pi - 1);
       quickSort(arr, pi + 1, high);
   }
}

void doQuickSort(long arr[], int high){
   cout<<"Quick sort performance "<<endl;
   cout << "Start time : " << currentDateTime() <<endl;
   auto start = high_resolution_clock::now();
   quickSort(arr,0,high);
   cout << "End time : " << currentDateTime() <<endl;
   auto stop = high_resolution_clock::now();
   auto duration = duration_cast<microseconds>(stop - start);
   cout << "Elapse time : " << duration.count() << " microseconds" << endl;
}

void copyArrayFunc(long source[],long dest[],int size){

   for(int i=0;i<size;i++){
       dest[i] = source[i];
   }
}

void merge(long arr[], int l, int m, int r)
{
   int i, j, k;
   int n1 = m - l + 1;
   int n2 = r - m;

   /* create temp arrays */
   int L[n1], R[n2];

   /* Copy data to temp arrays L[] and R[] */
   for (i = 0; i < n1; i++)
       L[i] = arr[l + i];
   for (j = 0; j < n2; j++)
       R[j] = arr[m + 1+ j];

   /* Merge the temp arrays back into arr[l..r]*/
   i = 0; // Initial index of first subarray
   j = 0; // Initial index of second subarray
   k = l; // Initial index of merged subarray
   while (i < n1 && j < n2)
   {
       if (L[i] <= R[j])
       {
           arr[k] = L[i];
           i++;
       }
       else
       {
           arr[k] = R[j];
           j++;
       }
       k++;
   }

   /* Copy the remaining elements of L[], if there
are any */
   while (i < n1)
   {
       arr[k] = L[i];
       i++;
       k++;
   }

   /* Copy the remaining elements of R[], if there
are any */
   while (j < n2)
   {
       arr[k] = R[j];
       j++;
       k++;
   }
}
void mergeSort(long arr[], int l, int r)
{
   if (l < r)
   {
       int m = l+(r-l)/2;
       mergeSort(arr, l, m);
       for(int i=l;i<=m;i++){
       }
       mergeSort(arr, m+1, r);

       for(int i=m+1;i<=r;i++){
       }
       merge(arr, l, m, r);
   }
}

void doMergeSort(long arr[], int r)
{
   cout<<"\n\nMerge sort performance "<<endl;
   auto start = high_resolution_clock::now();
   cout << "Start time : " << currentDateTime() <<endl;
   mergeSort(arr,0,r);
   cout << "End time : " << currentDateTime() <<endl;
   auto stop = high_resolution_clock::now();
   auto duration = duration_cast<microseconds>(stop - start);
   cout << "Elapse time : " << duration.count() << " microseconds" << endl;
}

int main()
{
   //initialize array of 1000
   long arraySize;
   cout<<"Enter input size : ";
   cin>>arraySize;
   long array[arraySize];
   long copyArray[arraySize];
   //set all to zero
   for(int i=0;i<arraySize;i++){
       array[i] =rand()%100000;
   }
   copyArrayFunc(array,copyArray,arraySize);

   insertionSort(copyArray,arraySize);
   cout<<endl<<endl<<endl;
   copyArrayFunc(array,copyArray,arraySize);
   selectionSort(copyArray,arraySize);
   cout<<endl<<endl<<endl;
   copyArrayFunc(array,copyArray,arraySize);
   doQuickSort(copyArray,arraySize-1);
   copyArrayFunc(array,copyArray,arraySize);
   doMergeSort(copyArray,arraySize-1);

   return 0;
}

output: