Sorting Algorithms in C: Bubble, Selection, Insertion, Merge, Quick, and Heap

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------    Practical -1        Aim- Implementation and Time analysis of sorting algorithms. : Bubble sort, Selection sort, Insertion sort, Merge sort and Quick sort.    Program-    1) Bubble sort     #include <stdio.h>    #include <time.h>    void  bubblesort ( int  a [] , int  n ) {     int  i , j , temp ;    for ( i = 0 ;  i < n ;  i ++) {    for ( j = 0 ;  j < n - i - 1 ;  j ++) {    if ( a [ j ]> a [ j + 1 ]) {    temp = a [ j ];    a [ j ]= a [ j + 1 ];    a [ j + 1 ]= temp ;    }    }    }    }    void  printarr ( int  a [] , int  n ) {    int  i ;    for ( i = 0 ;  i < n ;  i ++) {    printf ( " %d  " ,  a [ i ]);    }    }    void  main () {    double  time_spent = 0.0 ;    int  i , n ;    int  a [ 100000 ];    printf ( "Enter size of array: " );    scanf ( " %d " ,& n );     for ( i = n ;  i > 0 ;  i --) {    a [ n - i ]= i ;    }    clock_t  begin = clock ();    bubblesort ( a , n );    //   printarr(a,n);  clock_t  end  =  clock ();     time_spent +=( double )( end  -  begin ) /  CLOCKS_PER_SEC ;    printf ( "The elapsed time is  %f  seconds  \n " ,  time_spent );    }    SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 1 

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------    2) Selection sort     #include <stdio.h>    #include <time.h>    void  selectionsort ( int  a [] , int  n ) {    int  i , j , temp ;    for ( i = 0 ;  i < n - 1 ;  i ++) {    for ( j = i + 1 ;  j < n ;  j ++) {    if ( a [ i ]> a [ j ]) {    temp = a [ j ];    a [ j ]= a [ j + 1 ];    a [ j + 1 ]= temp ;    }    }     }    }    void  printarr ( int  a [] , int  n ) {    int  i ;    for ( i = 0 ;  i < n ;  i ++) {    printf ( " %d  " ,  a [ i ]);    }    }    void  main () {    double  time_spent = 0.0 ;    int  i , n ;    int  a [ 100000 ];    printf ( "Enter size of array: " );    scanf ( " %d " ,& n );    for ( i = n ;  i > 0 ;  i --) {    a [ n - i ]= i ;    }    clock_t  begin = clock ();    selectionsort ( a , n );    //   printarr(a,n);  clock_t  end  =  clock ();      time_spent +=( double )( end  -  begin ) /  CLOCKS_PER_SEC ;    printf ( "The elapsed time is  %f  seconds  \n " ,  time_spent );    }    3) Insertion sort     #include <stdio.h>    #include <time.h>    void  insertionsort ( int  a [] , int  n ) {    int  i ,  key ,  j ;    for  ( i  =  1 ;  i  <  n ;  i ++) {    key  =  a [ i ];    SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 2 

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------     j  =  i  -  1 ;    while  ( j  >=  0  &&  a [ j ] >  key ) {    a [ j  +  1 ] =  a [ j ];    j  =  j  -  1 ;    }    a [ j  +  1 ] =  key ;    }    }    void  printarr ( int  a [] , int  n ) {    int  i ;    for ( i = 0 ;  i < n ;  i ++) {    printf ( " %d  " ,  a [ i ]);     }    }    void  main () {    double  time_spent = 0.0 ;    int  i , n ;    int  a [ 100000 ];    printf ( "Enter size of array: " );    scanf ( " %d " ,& n );    for ( i = n ;  i > 0 ;  i --) {    a [ n - i ]= i ;    }    clock_t  begin = clock ();    insertionsort ( a , n );    //   printarr(a,n);  clock_t  end  =  clock ();     time_spent +=( double )( end  -  begin ) /  CLOCKS_PER_SEC ;    printf ( "The elapsed time is  %f  seconds  \n " ,  time_spent );    }    4) Merge sort     #include  <stdio.h>     #include  <stdlib.h>    #include <time.h>    void  merge ( int  arr [] ,  int  l ,  int  m ,  int  r )    {    int  i ,  j ,  k ;    int  n1  =  m  -  l  +  1 ;    int  n2  =  r  -  m ;    int  L [ n1 ],  R [ n2 ];    for  ( i  =  0 ;  i  <  n1 ;  i ++)    L [ i ] =  arr [ l  +  i ];    for  ( j  =  0 ;  j  <  n2 ;  j ++)    SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 3 

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------     R [ j ] =  arr [ m  +  1  +  j ];    i  =  0 ;    j  =  0 ;    k  =  l ;    while  ( i  <  n1  &&  j  <  n2 ) {    if  ( L [ i ] <=  R [ j ]) {    arr [ k ] =  L [ i ];    i ++;    }    else  {    arr [ k ] =  R [ j ];    j ++;     }    k ++;    }    while  ( i  <  n1 ) {    arr [ k ] =  L [ i ];    i ++;    k ++;    }    while  ( j  <  n2 ) {    arr [ k ] =  R [ j ];    j ++;    k ++;    }    }    void  mergeSort ( int  arr [] ,  int  l ,  int  r )    {    if  ( l  <  r ) {    int  m  =  l  + ( r  -  l ) /  2 ;    mergeSort ( arr ,  l ,  m );    mergeSort ( arr ,  m  +  1 ,  r );     merge ( arr ,  l ,  m ,  r );    }    }    void  printArray ( int  A [] ,  int  size )    {    int  i ;    for  ( i  =  0 ;  i  <  size ;  i ++)    printf ( " %d  " ,  A [ i ]);    printf ( " \n " );    }    void  main ()    SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 4 

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------     {    double  time_spent = 0.0 ;    int  i , n ;    int  a [ 100000 ];    printf ( "Enter size of array: " );    scanf ( " %d " ,& n );    for ( i = n ;  i > 0 ;  i --) {    a [ n - i ]= i ;    }    clock_t  begin = clock ();    mergeSort ( a , 0 , n - 1 );    clock_t  end  =  clock ();     time_spent +=( double )( end  -  begin ) /  CLOCKS_PER_SEC ;    printf ( "The elapsed time is  %f  seconds  \n " ,  time_spent );    }      5) Quick sort     #include  <stdio.h>    #include <time.h>    void  swap ( int *  a ,  int *  b )    {    int  t  = * a ;    * a  = * b ;    * b  =  t ;    }    int  partition  ( int  arr [] ,  int  low ,  int  high )    {    int  pivot  =  arr [ high ];    int  i  = ( low  -  1 );    for  ( int  j  =  low ;  j  <=  high  -  1 ;  j ++)    {     if  ( arr [ j ] <  pivot )    {    i ++;    swap (& arr [ i ], & arr [ j ]);    }    }    swap (& arr [ i  +  1 ], & arr [ high ]);    return  ( i  +  1 );    }    void  quickSort ( int  arr [] ,  int  low ,  int  high )    {    if  ( low  <  high )    {    SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 5 

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------     int  pi  =  partition ( arr ,  low ,  high );    quickSort ( arr ,  low ,  pi  -  1 );    quickSort ( arr ,  pi  +  1 ,  high );    }    }    void  main ()    {    double  time_spent = 0.0 ;    int  i , n ;    int  a [ 100000 ];    printf ( "Enter size of array: " );    scanf ( " %d " ,& n );     for ( i = n ;  i > 0 ;  i --) {    a [ n - i ]= i ;    }    clock_t  begin = clock ();    quickSort ( a , 0 , n - 1 );    clock_t  end  =  clock ();    time_spent +=( double )( end  -  begin ) /  CLOCKS_PER_SEC ;    printf ( "The elapsed time is  %f  seconds  \n " ,  time_spent );    }      6) Heap sort     #include  <stdio.h>    #include <time.h>    void  swap ( int *  a ,  int *  b )    {    int  temp = *a;    *a = *b;    *b = temp;    }     void  heapify ( int  arr [] ,  int  N ,  int  i )    {    int  largest = i;    int  left =  2  * i +  1 ;    int  right =  2  * i +  2 ;    if  (left < N &&  arr [left] >  arr [largest])    largest = left;    if  (right < N &&  arr [right] >  arr [largest])    largest = right;    if  (largest != i) {    swap (& arr [i], & arr [largest]);      SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 6 

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms  Enrollment No: 200420107127   Name: Lathiya Dhruvil  Date: 27/07/2022    ----------------------------------------------------------------------------------------------------------------------------------     heapify (arr, N, largest);    }    }    void  heapSort ( int  arr [] ,  int  N )    {    for  ( int  i = N /  2  -  1 ; i >=  0 ; i--)  heapify (arr, N, i);  for  ( int  i = N -  1 ; i >=  0 ; i--) {  swap (& arr [ 0 ], & arr [i]);  heapify (arr, i,  0 );  }      }     void  main ()    {    double  time_spent= 0.0 ;    int  i,n;    int  a [ 100000 ];    printf ( "Enter size of array: " );    scanf ( " %d " ,&n);    for (i=n; i> 0 ; i--) {    a [n-i]=i;    }    clock_t  begin= clock ();    heapSort (a,n);    clock_t  end =  clock ();    time_spent+=( double )(end - begin) / CLOCKS_PER_SEC;    printf ( "The elapsed time is  %f  seconds  \n " , time_spent);    }          Time complexity        n  10  100  1000  10000  50000  Bubble  0.000  0.000  0.118  0.975  6.657  sort            Selection  0.000  0.000  0.005  0.290  7.545  sort            Insertion  0.000  0.000  0.002  0.177  4.577  sort            Merge  0.000  0.000  0.0002  0.0030  0.0115  Sort            Quick sort  0.000  0.000  0.0048  0.2156  5.3881  Heap sort  0.000  0.000  0.0001  0.0035  0.0121  SCET/CO/2022-23/Odd/BE Div-I/Sem-V      Page No.- 7   

Subject code: 3150703   Subject Name: Analysis and Design of Algorithms   Date: 27/07/2022  Enrollment No: 200420107127   Name: Lathiya Dhruvil  ----------------------------------------------------------------------------------------------------------------------------------    Graph analysis for different sorting algorithm    1) Bubble sort   2) Selection sort      60000            50000            40000            30000            20000            10000            0            -10000  1  2  3  4  5                  60000            50000            40000            30000            20000            10000            0            -10000  1  2  3  4  5                3) Insertion sort     60000          50000          40000          30000          20000          10000          0          1  2  3  4  5  -10000              5) Quick sort     60000            50000            40000            30000            20000            10000            0            -10000  1  2  3  4  5            -20000                  4) Merge sort      60000            50000            40000            30000            20000            10000            0            -10000  1  2  3  4  5            -20000                 6) Heap sort     60000          50000          40000          30000          20000          10000          0          1  2  3  4  5  -10000                            SCET/CO/2022-23/Odd/BE Div-I/Sem-V   Page No.- 8