C++ Programming Homework Solution - Implement Three Sorting Routines of your choice

Question

Implement three sorting routines of your choice.

• One must be not quadratic (e.g. quicksort, heapsort, mergesort, or shellsort).  
• Create input files of four sizes: 5000, 10000, 20000, and 50000 integers.
• For each size file make 3 versions. One version will be randomly ordered, one version will be in descending order, and one version will be in ascending order. This means you have a set of 12 input files. Run each sort against all input files.
• Thus, you will run average case, worst case (descending) and best case (ascending). For each run, access the system clock to get time values. The call to the clock should be placed as closely as possible to the beginning and end of each sort.
• Turn in a commentary comparing the three sorts and their performance.
• Comment on the relative run times between the different sorts, the effect of the order of the data (ascending, descending, or random). Include plots of run time versus file size.
• Comment on how the size of the file is related to the run time and the computational complexity indicated by the plots. 
• Time the sorts several times to get an average.
   

C++ Program Solution

#include
#include
#include 
#include
#include
#include

/* The functions below are to get the time stamps. These are standard cpp functions to generate
current system time to milliseconds of precision. */

int getMilliCount()
{
  timeb tb;
  ftime(&tb);
  int nCount = tb.millitm + (tb.time & 0xfffff) * 1000;
  return nCount;
}

int getMilliSpan(int nTimeStart)
{
  int nSpan = getMilliCount() - nTimeStart;
  if(nSpan < 0)
    nSpan += 0x100000 * 1000;
  return nSpan;
}

using namespace std;

/* The function prints the contents of the integer array one per line
to the file output.txt. It accepts the array and its size as arguments. */

void PrintArray(int arr[], int size)
{
  FILE *fpOut;
  fpOut = fopen("output.txt", "w");
  for(int i=0;i   {
    fprintf(fpOut,"%d\n",arr[i]);
  }
  fclose(fpOut);
}

/*Selection sort - accepts the array, and its size as arguments. Sorts the
array using selection sort. Starts the counter just before sorting commences, and
prints the total time elapsed during sorting immediately after sorting is done. */

void SelectionSort(int arr[], int size)
{
  std::cout<<"\nSorting using selection sort...";
  int start = getMilliCount();

  int i,j,temp,min_idx;  
  
  //Standard text book algorithm for selection sort.

  for (i = 0;i   {  
    min_idx = i;                  
    for (j = i+1;j       if(arr[j] < arr[min_idx])  
        min_idx = j;  

    temp = arr[min_idx];            //Swap the elements at indices i and min_idx
    arr[min_idx] = arr[i];
    arr[i] = temp;
  }

  int milliSecondsElapsed = getMilliSpan(start);

  printf("\n\nElapsed time = %u milliseconds", milliSecondsElapsed);

}

/*Bubble sort - accepts the array, and its size as arguments. Sorts the
array using selection sort. Starts the counter just before sorting commences, and
prints the total time elapsed during sorting immediately after sorting is done. */

void BubbleSort(int arr[], int size)
{
  std::cout<<"\nSorting using Bubble sort...";
  time_t my_time = time(NULL); 
  printf("\nTime is %s", ctime(&my_time)); 

  int i, j, temp; 

  //Standard textbook algorithm for bubble sort.

  for (i=0;i     for (j =0;j       if (arr[j]>arr[j+1])          //If an element is larger than the one next to it, swap
      {
         temp = arr[j];
         arr[j] = arr[j+1];
         arr[j+1] = temp;
      }

  printf("\nSorting complete.");
  my_time = time(NULL); 
  printf("\nTime is %s", ctime(&my_time)); 
}

/*Helper function for MergeSort. This function will merge two sorted arrays into one
sorted array. Traverse both arrays from left to right, compare the elements from the two arrays, 
and advance accordingly. An implementation of the standard textbook merge-sort algorithm. */

void Merge(int arr[], 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 < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    i = 0;
    j = 0;
    k = l;

    /*Compare the ith element of array L with the jth element of array R.
    Then, add to array arr whichever is smaller. Increment i (or j) accordingly.
    Then, compare again. Do this, until i is < size of L, and j is < size of R. Standard algorithm. */

    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    /*Now, if any elements remain in either L or R after the above loop is over, 
    copy-paste them into the array arr. Sorting is now complete. */

    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 

/*Merge sort - accepts the array, and the left and right indices as arguments. Sort the sub-array from 
left to middle, sort the sub-array from middle to right, and then merge the two sub-arrays. Standard merge
sort algorithm */

void MergeSort(int arr[], int left, int right)
{
  if (left < right) 
  { 
    int middle = left+(right-left)/2; 
    MergeSort(arr, left, middle);           //Sort the left sub-array
    MergeSort(arr, middle+1, right);        //Sort the right sub-array
    Merge(arr, left, middle, right);        //Now, merge the two sorted sub-arrays
  } 
}

int main() 
{
  char fname[100];
  std::cout << "Enter file name:\n";
  std::cin >> fname;

  FILE *fpIn;

  if (!(fpIn = fopen(fname, "r")))
  {
    printf("Sorry, the file could not be opened for input.");
    exit (1);
  }

  printf("\nOpened the file. Reading data...");

  int i=0,num[50000];
  while (!feof(fpIn))
  {
      fscanf(fpIn, "%d\n",&num[i]);
      ++i;
  }

  int choice;
  std::cout<<"\n\nSelect the sorting technique\n";
  std::cout<<"1. Selection sort O(n square)\n2. Bubble sort O(n square)\n3. Merge sort O(n log n)\nYour choice :";
  std::cin>>choice;

  //Call the appropriate sorting function according to the user's choice.

  if(choice==1)
    SelectionSort(num,i);
  else if(choice==2)
    BubbleSort(num,i);
  else if(choice==3)
  {
    std::cout<<"\nSorting using merge sort...";       //For merge sort, timer is started from the main, because there is a recursive call.
    time_t my_time = time(NULL); 
    printf("\nTime is %s", ctime(&my_time)); 
    MergeSort(num,0,i-1);
    printf("\nSorting complete.");
    my_time = time(NULL); 
    printf("\nTime is %s", ctime(&my_time)); 
  }
  else
  {
    std::cout<<"\nInvalid choice";
    exit(0);
  }

  std::cout<<"\nSorted array is available in output.txt";
  PrintArray(num,i);
  fclose(fpIn);
  return 0;

}