Write a program to display the running time of Bubble Sort a

Write a program to display the running time of Bubble Sort and Merge Sort.
the C++ code of Bubble Sort and Merge Sort .
Test these sorts on arrays of various sizes. Arrays of the same size should contain identical entries
to test each sort solution.
Use the function clock from <ctime> to calculate the run times each of the two sorts.
Include best / worst cases for each sort.
display a table of the overall run time , along with the number of comparisons and the number of
swaps of each sort solution for a various of n.

Solution

The runtime execution of Bubble sort and Merge sort can be tested well using below code. The time taken for sorting using both Bubble sort and Merge sort methods is implemented on set of arrays with varying lengths.

Below program is tested by reading a input file which contains 300000 integers stored randomly.

To generate the input file that will be feed to the main program is as below:

(Program to store 300000 random integers in the .dat file)

*****************************************************************************

#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;
const size_t length = 300000;

int main()
{
    ofstream fout(\"random.dat\", ios::binary);
    srand(time(NULL));
    int r;
    for (size_t i = 0; i < length; i++)
    {
        r = rand();
        fout.write((char*)&r, sizeof(r));
    }
    fout.close();
    return 0;
}

***********************************************************************************************

Below is the main program with implementation to find the runtime execution (time in seconds) of Bubble sort and Merge Sort for various lengths arrays.

****************************************************************************************************************

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

long length = 1000;
const long max_length = 300000;

int list[max_length];

void read()
{
    ifstream fin(\"random.dat\", ios::binary);
    for (long i = 0; i < length; i++)
    {
        fin.read((char*)&list[i], sizeof(int));
    }
    fin.close();
}

void bubbleSort()
{
    int temp;
    for(long i = 0; i < length; i++)
    {
        for(long j = 0; j < length-i-1; j++)
        {
            if (list[j] > list[j+1])
            {
                temp        = list[j];
                list[j]     = list[j+1];
                list[j+1]   = temp;
            }
        }
    }
}

void merge(long l, long m, long r)
{
    long i, j, k;
    long n1 = m - l + 1;
    long 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] = list[l + i];
    for (j = 0; j < n2; j++)
        R[j] = list[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            list[k] = L[i];
            i++;
        }
        else
        {
            list[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there are any */
    while (i < n1)
    {
        list[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there are any */
    while (j < n2)
    {
        list[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(long left, long right)
{
   if (left < right)
   {
      long mid = left+(right-left)/2; //Same as (left+right)/2 but avoids overflow for large left & right
      mergeSort(left, mid);
      mergeSort(mid+1, right);
      merge(left, mid, right);
   }
}

int main()
{
    double t1, t2;

    for (length = 1000; length <= max_length; )
    {
        cout << \"\ Length\\t: \" << length << \'\ \';

        read();
        t1 = clock();
        bubbleSort();
        t2 = clock();
        cout << \"Bubble Sort\\t: \" << (t2 - t1)/CLK_TCK << \" sec\ \";


        read();
        t1 = clock();
        mergeSort(0, length - 1);
        t2 = clock();
        cout << \"Merge Sort\\t: \" << (t2 - t1)/CLK_TCK << \" sec\ \";

        switch (length)
        {
        case 1000 :
            length = 5000;
            break;
        case 5000 :
            length = 10000;
            break;
        case 10000 :
            length = 50000;
            break;
        case 50000 :
            length = 100000;
            break;
        case 100000 :
            length = 200000;
            break;
        case 200000 :
            length = 300000;
            break;
        case 300000 :
            length = 300001;
            break;
        }
    }

    return 0;
}

******************************************************************************************************************

above code is working for arrays with lengths : 1000, 5000, 10000, 50000, 100000, 200000, 300000 integers.

The code may take several minutes to sort and compute the time taken for different lenghts of array using both bubble and merge sort.

Note: If you don\'t want to test such big size arrays then the input file generated can be created with small size. But significant change in the runtime will be not seen in that case.

Below table will give you an idea about time taken for sorting at different lengths using Bubble and Merge sort