Compare and plot the graph of CPU time for different sorting algorithms- bubble sort, selection sort, insertion sort for different cases

 Compare the CPU time of bubble sort, insertion and selection sort for different cases.

a)     When the inputs are sorted in increasing order

CODE:

#include <stdio.h>

#include <stdlib.h>

#include<time.h>

void swap( int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

void bubble_Sort(int a[],  int n)

{

      int i,j;

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

        {

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

         {

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

            {

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

            }

         }

        }

}

void selection_Sort( int a[],  int n)

{

     int i, j, min;

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

    {

         min = i;

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

        {

            if (a[j] < a[min])

                min = j;

        }

        swap(&a[min], &a[i]);

    }

}

void insertion_Sort(int a[], int n)

{

    int i, j, check;

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

    {

        check= a[i];

        j = i - 1;

        while (j >= 0 && a[j] > check)

        {

            a[j + 1] = a[j];

            j = j - 1;

        }

        a[j + 1] = check;

    }

}

int main()

{

        int n;

        printf("enter the value of n\n");

        scanf("%d",&n);

         double bubbletime, selecttime, inserttime;

         int *a=(int*)malloc(n*sizeof(int));

        int *b=(int*)malloc(n*sizeof(int));

        int *c=(int*)malloc(n*sizeof(int));

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

        {

            int no= i;

            a[i]=no;

             b[i]=no;

             c[i]=no;

        }

         clock_t start;

         start = clock();

        bubble_Sort(a, n);

        start = clock()-start;

        bubbletime = ((double)(start));

        start = clock();

        selection_Sort(b, n);

        start = clock()-start;

        selecttime = ((double)(start));

        start = clock();

        insertion_Sort(c, n);

        start = clock()-start;

        inserttime = ((double)(start));

       printf("bubblesort time= %lf\n selectionsort time= %lf\n insertionsort time=               %lf\n",bubbletime,selecttime,inserttime);

 return 0;

}

OUTPUT:

b) when inputs are sorted in decreasing order

#include <stdio.h>

#include <stdlib.h>

#include<time.h>

void swap( int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

void bubble_Sort(int a[],  int n)

{

      int i,j;

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

        {

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

         {

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

            {

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

            }

         }

        }

}

void selection_Sort( int a[],  int n)

{

     int i, j, min;

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

    {

         min = i;

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

        {

            if (a[j] < a[min])

                min = j;

        }

        swap(&a[min], &a[i]);

    }

}

void insertion_Sort(int a[], int n)

{

    int i, j, check;

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

    {

        check= a[i];

        j = i - 1;

        while (j >= 0 && a[j] > check)

        {

            a[j + 1] = a[j];

            j = j - 1;

        }

        a[j + 1] = check;

    }

}

int main()

{

        int n;

        printf("enter the value of n\n");

        scanf("%d",&n);

        double bubbletime, selecttime, inserttime;

       int *a=(int*)malloc(n*sizeof(int));

        int *b=(int*)malloc(n*sizeof(int));

        int *c=(int*)malloc(n*sizeof(int));

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

        {

            int no= i;

            a[i]=no;

            b[i]=no;

            c[i]=no;

          }

        clock_t start;

        start = clock();

        bubble_Sort(a, n);

        start= clock()-start;

       bubbletime = ((double)(start))/CLOCKS_PER_SEC;

         start = clock();

        selection_Sort(b, n);

        start = clock()-start;

         selecttime = ((double)(start))/CLOCKS_PER_SEC;

         start = clock();

        insertion_Sort(c, n);

        start = clock()-start;

        inserttime = ((double)(start));

        printf("bubblesort time= %lf\n selectionsort time= %lf\n insertionsorttime= %lf\n",bubbletime,selecttime,inserttime);

    return 0;

}

OUTPUT:

c) When the inputs are random( inputs are generated randomly)

CODE:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void swap( int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

void bubble_Sort(int a[],  int n)

{

      int i,j;

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

        {

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

         {

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

            {

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

            }

         }

        }

}

void selection_Sort( int a[],  int n)

{

     int i, j, min;

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

    {

         min = i;

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

        {

            if (a[j] < a[min])

                min = j;

        }

        swap(&a[min], &a[i]);

    }

}

void insertion_Sort(int a[], int n)

{

    int i, j, check;

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

    {

        check= a[i];

        j = i - 1;

        while (j >= 0 && a[j] > check)

        {

            a[j + 1] = a[j];

            j = j - 1;

        }

        a[j + 1] = check;

    }

}

int main()

{

        int n;

        printf("enter the value of n\n");

        scanf("%d",&n);

        double bubbletime, selecttime, inserttime;

        int *a=(int*)malloc(n*sizeof(int));

        int *b=(int*)malloc(n*sizeof(int));

        int *c=(int*)malloc(n*sizeof(int));

        srand(time(0));

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

        {

            int no= rand() %n +1;

            a[i]=no;

            b[i]=no;

            c[i]=no;

        }

        clock_t start;

        start = clock();

        bubble_Sort(a, n);

        start= clock()-start;

        bubbletime = ((double)(start));

        start = clock();

        selection_Sort(b, n);

        start= clock() -start;

        selecttime = ((double)(start));

        start = clock();

        insertion_Sort(c, n);

        start= clock()-start;

        inserttime = ((double)(start));

        printf("bubblesort time= %lf\n selectionsort time= %lf\n insertionsort time= %lf\n",bubbletime,selecttime,inserttime);

    return 0;

}

OUTPUT:

   GRAPH: