Question

Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort, and selection sort.

It must show how long it took and how many movements occurred.

Please write codes in C++

Here's data set (should be stored in txt file)

7426
4524
4737
9436
3997
2757
6288
5414
9590
5968
6638
3199
9514
1541
9866
2144
6731
911
2171
6135
6437
912
9417
2662
6606
6349
707
2890
5386
9718
3492
5068
9674
8578
8323
7789
4748
7576
2664
6352
7967
8556
4740
5737
6764
368
1070
3700
1291
5279
9429
9507
2575
3099
2147
9660
2515
2976
4086
8305
6913
1308
7123
7678
8971
7507
139
51
5980
1100
3976
7289
9249
1662
8659
2758
3605
1079
7829
2298
3671
8901
1176
9089
3350
7500
6702
8903
5279

Answer 1

/*
 *  C++11 Program to find time elapsed in differnet sorting algorithm
 */

#include <bits/stdc++.h>
using namespace std;
using namespace std :: chrono;
#define MAX 100

void selectionSort(int arr[], int n)
{
  int i, j;
  
  for (j = 0; j < n - 1; j++) {
    int iMin = j;

    for (i = j + 1; i < n; i++) {
      if (arr[i] < arr[iMin]) {
        iMin = i;
      }
    }

    if (iMin != j) {
      int temp = arr[j];
      arr[j] = arr[iMin];
      arr[iMin] = temp;
    }
  }
}

void quickSort(int arr[], int first_index, int last_index)
{
  int pivotIndex, temp, index_a, index_b;

  if (first_index < last_index) {
    pivotIndex = first_index;
    index_a = first_index;
    index_b = last_index;

    while (index_a < index_b) {
      while (arr[index_a] <= arr[pivotIndex] && index_a < last_index) {
        index_a++;
      }
      while (arr[index_b] > arr[pivotIndex]) {
        index_b--;
      }

      if (index_a < index_b) {
        temp = arr[index_a];
        arr[index_a] = arr[index_b];
        arr[index_b] = temp;
      }
    }

    temp = arr[pivotIndex];
    arr[pivotIndex] = arr[index_b];
    arr[index_b] = temp;

    quickSort(arr, first_index, index_b - 1);
    quickSort(arr, index_b + 1, last_index);
  }
}

void shellSort(int arr[], int n)
{
  int j;

  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; ++i) {
      int temp = arr[i];
      for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

int main()
{
  int arr[MAX], i = 0, size = 0;

  ifstream file("data.txt");

  while (!file.eof())
  {
    file >> arr[i];
    i++;
  }

  size = i;

  //  selection sort
  auto startSel = high_resolution_clock :: now();
  selectionSort(arr, size);
  auto stopSel = high_resolution_clock :: now();
  auto durationSel = duration_cast<microseconds>(stopSel - startSel);
  cout << "Time taken by selection sort: " << durationSel.count() << " microseconds" << endl;

  //  quick sort
  auto startQuick = high_resolution_clock :: now();
  quickSort(arr, 0, size - 1);
  auto stopQuick = high_resolution_clock :: now();
  auto durationQuick = duration_cast<microseconds>(stopQuick - startQuick);
  cout << "Time taken by quick sort: " << durationQuick.count() << " microseconds" << endl;

  //  shell sort
  auto startShel = high_resolution_clock :: now();
  shellSort(arr, size);
  auto stopShel = high_resolution_clock :: now();
  auto durationShel = duration_cast<microseconds>(stopShel - startShel);
  cout << "Time taken by shell sort: " << durationShel.count() << " microseconds" << endl;

  return 0; 
}

/*  Program ends here */

data file