Question

For this program, you will be working with data from the NASA website which lists Near Earth Objects detected by the JPL Sentry System. You are given a text file listing the designation and impact probability (with Earth, generally within the next 100 years) of 585 Near Earth Objects. Your job will be to sort these objects by their impact probabilities.

Input File Format

The input file contains 585 records. Each record is on a separate line. Each line contains a designation string and an impact probability. The designation string contains no spaces. There is a space between the designation string and the impact probability. The impact probability is a floating point number. Below are three example records from the input file:

2015_KP18 0.00004000000 2015_MN11 0.00000510000 2015_KR157 0.00000000030

Sorting Algorithm Requirements

For this assignment, you will implement two different sorting techniques and examine their performances: MergeSort and QuickSort. Do not use a C/C++ library for the sorting. You must write your own code to perform the sorting operations. For QuickSort, choose the pivot using the median-of-three approach. You must write a separate program for each of these two sorting techniques. Your programs should time the execution time for each sorting method. http://www.cplusplus.com/reference/ctime/clock/ provides a simple mechanism for timing code using clicks. Only time the sort routines, not the entire program.

Program Input/Output Requirements

Your programs must use standard input with file redirection (similar to Programming Assignment 1). Each of your two programs must create a new file named neo_sorted.txt which contains the records from the input file sorted in ascending order of impact probability. The format of the output file must be identical to that of the input file. The only difference between the input file and output file will be the order of the records.

Each of your two programs must also print the number of clicks taken by the sorting procedure.

Answer 1

#include <iostream>
#include <string>
#include <time.h>
using namespace std;

void swap(int* a, int* b)
{
   int t = *a;
   *a = *b;
   *b = t;
}

void merge(int *a, int low, int high, int mid)
{
   int i, j, k, c[50];
   i = low;
   k = low;
   j = mid + 1;
   while (i <= mid && j <= high)
   {
       if (a[i] < a[j])
       {
           c[k] = a[i];
           k++;
           i++;
       }
       else
       {
           c[k] = a[j];
           k++;
           j++;
       }
   }
   while (i <= mid)
   {
       c[k] = a[i];
       k++;
       i++;
   }
   while (j <= high)
   {
       c[k] = a[j];
       k++;
       j++;
   }
   for (i = low; i < k; i++)
   {
       a[i] = c[i];
   }
}
void mergesort(int *a, int low, int high)
{
   int mid;
   if (low < high)
   {
       mid = (low + high) / 2;
       mergesort(a, low, mid);
       mergesort(a, mid + 1, high);
       merge(a, low, high, mid);
   }
   return;
}
//Quick sort
int partition(int arr[], int l, int h)
{
   int x = arr[h]; // pivot
   int i = (l - 1);

   for (int j = l; j <= h - 1; j++)
   {
      
       if (arr[j] <= x)
       {
           i++;   
           swap(&arr[i], &arr[j]);
       }
   }
   swap(&arr[i + 1], &arr[h]);
   return (i + 1);
}

void quickSort(int arr[], int l, int h)
{
   if (l < h)
   {
       int p = partition(arr, l, h);
       quickSort(arr, l, p - 1);
       quickSort(arr, p + 1, h);
   }
}

int main()
{
   //Read data
   int *a; //you can define a struct to include string and impact and then use the impact
   //I'll focus on core part, i.e merge sort and quick sort
   clock_t t = clock();
   mergesort(a, 0, 584); //Since 585 no of records are there
   t = clock() - t;
   cout << "It took me " << ((float)t) / CLOCKS_PER_SEC << " seconds for merge sort" << endl;]
   t = clock();
   quickSort(a, 0, 584);
   t = clock() - t;
   cout << "It took me " << ((float)t) / CLOCKS_PER_SEC << " seconds for quick sort" << endl; ]
   system("pause");
   return 0;
}