Answer to Question #284081 in C++ for Umar

Question

Develop a c++ program that acts as simulator for your bubble sort and insertion sort Algorithm .and measure there time complexity by calculating there rare time of execution for three different types of data .

No#: Sorted array of low data elements

No2#: reversely decreasing order based array of two elements and finally randomly placed array pf (low element).

Answer 1

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>


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


    void bubbleSort(long int a[], long int n)
    {
        for (long int i = 0; i < n - 1; i++) {
            for (long int j = 0; j < n - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(&a[j], &a[j + 1]);
                }
            }
        }
    }


    void insertionSort(long int arr[], long int n)
    {
        long int i, bar, j;
        for (i = 1; i < n; i++) {
            bar = arr[i];
            j = i - 1;


            while (j >= 0 && arr[j] > bar) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = bar;
        }
    }


    int main()
    {
        long int n = 10000;
        int foo = 0;


        double tim1[10], timeCalcArray[10];


        while (foo++ < 10) {
            long int a[n], b[n], c[n];


            for (int i = 0; i < n; i++) {
                long int no = rand() % n + 1;
                a[i] = no;
                b[i] = no;
                c[i] = no;
            }


            clock_t start, end;


            start = clock();
            bubbleSort(a, n);
            end = clock();


            tim1[foo] = ((double)(end - start));


            start = clock();
            insertionSort(b, n);
            end = clock();


            timeCalcArray[foo] = ((double)(end - start));


            printf("%li, %li, %li\n",
                n,
                (long int)tim1[foo],
                (long int)timeCalcArray[foo]);


            n += 10000;
        }


        return 0;
    }