Question

Write a C++ code for these 2 questions

1. Create an integer variable named ‘arraySize’ and initialize the value to 1000.

2.. Open an output file named ‘GroupAssignment2Results.csv’. The first line of this file should be the column headings: ‘Array Size’, ‘Bubble Sort Time’, ‘Selection Sort Time’, ’Insertion Sort Time’, ‘Quick Sort Time’, ‘Merge Sort Time’.

Answer 1

///////////////////////

///// run in visual studio , other compiler can not identify chrono

// chrono use for time calculation

////////////////////////

// header file

#include<iostream>
#include<fstream>
#include<cstdlib>
#include<chrono>

using namespace std;
using namespace std::chrono;

// bubble sort algorithm

void bubbleSort(int *a, int size) {
   for (int i = 0; i<size - 1; i++) {
       for (int j = 0; j<size - i - 1; j++) {
           if (a[j]>a[j + 1]) {
               //swap
               int temp = a[j];
               a[j] = a[j + 1];
               a[j + 1] = temp;
           }
       }
   }
}

// selection sort

void selectionSort(int *a, int size) {
   for (int i = 0; i<size - 1; i++) {
       int m_i = i;
       for (int j = i + 1; j<size; j++) {
           if (a[j]<a[m_i]) {
               m_i = j;
           }
       }
       //swap
       int temp = a[i];
       a[i] = a[m_i];
       a[m_i] = a[i];

   }
}

// insertion sort

void insertionSort(int *a, int size) {

   for (int i = 1; i<size; ++i) {
       int key = a[i];
       int j=i-1;

       for (; (j >= 0 && key < a[j]); j--) {
           a[j + 1] = a[j];
       }
      
       a[j + 1] = key;
   }

}

// make partition on array

int getPartition(int *a, int l, int h) {
   int pvt = a[h];
   int i = (l - 1);

   for (int j = l; j <= h - 1; j++) {
       if (a[j]<pvt) {
           i++;
           //swap
           int tmp = a[i];
           a[i] = a[j];
           a[j] = tmp;

       }
   }

   //swap
   int tmp = a[i + 1];
   a[i + 1] = a[h];
   a[h] = tmp;

   return(i + 1);
}

// quick sort
void quickSort(int *a, int l, int h) {
   if (l<h) {
       int p = getPartition(a, l, h);

       quickSort(a, l, p - 1);
       quickSort(a, p + 1, h);
   }
}

// merge array

void merge(int *a, int l, int m, int r) {
   int n1 = m - l + 1;
   int n2 = r - m;

   int *L = new int[n1];
   int *R = new int[n2];

   for (int i = 0; i<n1; i++) {
       L[i] = a[i + l];
   }
   for (int j = 0; j<n2; j++) {
       R[j] = a[m + j + 1];
   }

   int i = 0, j = 0, k = 1;

   while (i<n1 && j<n2) {
       if (L[i] <= R[j]) {
           a[k] = L[i];
           i++;
       }
       else {
           a[k] = R[j];
           j++;
       }
       k++;
   }

   while (i<n1) {
       a[k] = L[i];
       i++;
       k++;
   }

   while (j<n2) {
       a[k] = R[j];
       j++;
       k++;
   }

}
// merge sort

void mergeSort(int *a, int l, int r) {
   if (l<r) {
       int m = l + (r - l) / 2;
       mergeSort(a, l, m);
       mergeSort(a, m + 1, r);

       merge(a, l, m, r);
   }
}

int* randomData(int size) {
   int *ar = new int[size];

   for (int i = 0; i<size; i++) {
       ar[i] = rand();
   }

   return(ar);
}

void copyAry(int *a, int *b, int size) {
   for (int i = 0; i < size; i++) {
       a[i] = b[i];
   }
}

int main() {

   int arraySize = 1000;

   int *arrLst = new int[arraySize];
   int *arLst = new int[arraySize];

   arrLst = randomData(arraySize);
   //copy array
   // because after sorting arry will be sorted

   copyAry(arLst, arrLst, arraySize);

   auto start1 = high_resolution_clock::now();
   bubbleSort(arLst, arraySize);
   auto end1 = high_resolution_clock::now();
   auto duration1 = duration_cast<microseconds>(end1 - start1);
   cout << duration1.count()<<endl;

   // copy array for new sort
   copyAry(arLst, arrLst, arraySize);

   auto start2 = high_resolution_clock::now();
   selectionSort(arLst, arraySize);
   auto end2 = high_resolution_clock::now();
   auto duration2 = duration_cast<microseconds>(end2 - start2);
   cout << duration2.count() << endl;

   // copy array for new sort
   copyAry(arLst, arrLst, arraySize);

   auto start3 = high_resolution_clock::now();
   insertionSort(arLst, arraySize);
   auto end3 = high_resolution_clock::now();
   auto duration3 = duration_cast<microseconds>(end3 - start3);
   cout << duration3.count() << endl;

   // copy array for new sort
   copyAry(arLst, arrLst, arraySize);

   auto start4 = high_resolution_clock::now();
   mergeSort(arLst, 0,arraySize-1);
   auto end4 = high_resolution_clock::now();
   auto duration4 = duration_cast<microseconds>(end4 - start4);
   cout << duration4.count() << endl;

   // copy array for new sort
   copyAry(arLst, arrLst, arraySize);

   auto start5 = high_resolution_clock::now();
   quickSort(arLst, 0,arraySize-1);
   auto end5 = high_resolution_clock::now();
   auto duration5 = duration_cast<microseconds>(end5 - start5);
   cout << duration5.count() << endl;

   ofstream out("GroupAssignment2Results.csv");
   out << "Array Size,Bubble Sort Time,Selection Sort Time,Insertion Sort Time,Quick Sort Time,Merge Sort Time\n";
   out << arraySize << "," << duration1.count() << "," << duration2.count() << "," << duration3.count() << "," << duration5.count() << "," << duration4.count();

   cout << "\nOutput in File.";
      
   out.close();
   cin.get();

   return(0);
}