Question

Add bubble sort, radix sort, insertion sort, and merge sort to the code provided.

Import a data set (txt file) then do the sorting algorithm to measure 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

Here's the code

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

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;
}

Answer 1

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

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;
}
}
}

void bubbleSort(int arr[], int n)

{

   int i, j;

   bool swapped;

   for (i = 0; i < n-1; i++)

   {

     swapped = false;

     for (j = 0; j < n-i-1; j++)

     {

        if (arr[j] > arr[j+1])

        {

           swap(&arr[j], &arr[j+1]);

           swapped = true;

        }

     }

  

     // IF no two elements were swapped by inner loop, then break

     if (swapped == false)

        break;

   }

}

//radix sort

void radixsort(int arr[], int n)

{

    // Find the maximum number to know number of digits

    int m = getMax(arr, n);

     

    for (int exp = 1; m/exp > 0; exp *= 10)

        countSort(arr, n, exp);

}

int getMax(int arr[], int n)

{

    int max = arr[0];

    for (int i = 1; i < n; i++)

        if (arr[i] > max)

            max = arr[i];

    return max;

}

void countSort(int arr[], int n, int exp)

{

    int output[n]; // output array

    int i, count[10] = {0};

  

    // Store count of occurrences in count[]

    for (i = 0; i < n; i++)

        count[ (arr[i]/exp)%10 ]++;

  

    // Change count[i] so that count[i] now contains actual

    // position of this digit in output[]

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];

  

    // Build the output array

    for (i = n - 1; i >= 0; i--)

    {

        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

        count[ (arr[i]/exp)%10 ]--;

    }   

    // Copy the output array to arr[], so that arr[] now

    // contains sorted numbers according to current digit

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

//insertion sort

void insertionSort(int arr[], int n)

{

    int m, key,l;

    for (m = 1; m < n; m++)

    {

        key = arr[m];

       l = m- 1;

  

        /* Move elements of arr[0..i-1], that are

        greater than key, to one position ahead

        of their current position */

        while (l >= 0 && arr[l] > key)

        {

            arr[l+ 1] = arr[l];

          l =l - 1;

        }

        arr[l + 1] = key;

    }

//merge sort

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        // Same as (l+r)/2, but avoids overflow for

        // large l and h

        int m = l+(r-l)/2;

  

        // Sort first and second halves

        mergeSort(arr, l, m);

        mergeSort(arr, m+1, r);

  

        merge(arr, l, m, r);

    }

}

void merge(int 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 any */

      

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

  

    /* Copy the remaining elements of R[], if there any*/

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

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;

//bubble sort

auto startCel = high_resolution_clock :: now();
bubbleSort(arr, size);
auto stopCel = high_resolution_clock :: now();
auto durationCel = duration_cast<microseconds>(stopCel - startCel);
cout << "Time taken by bubble sort: " << durationCel.count() << " microseconds" << endl;

//radix sort

auto startCell = high_resolution_clock :: now();
radixsort(arr, size);
auto stopCell = high_resolution_clock :: now();
auto durationCell = duration_cast<microseconds>(stopCell - startCell);
cout << "Time taken by radix sort: " << durationCell.count() << " microseconds" << endl;

//insertion sort

auto startShel1 = high_resolution_clock :: now();
insertionsort(arr, size);
auto stopShel1 = high_resolution_clock :: now();
auto durationShel1 = duration_cast<microseconds>(stopShel1 - startShel1);
cout << "Time taken by insertion sort: " << durationShel1.count() << " microseconds" << endl;

//merge sort

auto startShell1 = high_resolution_clock :: now();
mergeSort(arr, 0, size - 1);
auto stopShell1 = high_resolution_clock :: now();
auto durationShell1 = duration_cast<microseconds>(stopShell1 - startShell1);
cout << "Time taken by merge sort: " << durationShell1.count() << " microseconds" << endl;

return 0;
}