Write a program to implement Heap sort Also implement one of

Write a program to implement Heap sort. Also implement one of the slow sorts (Bubble, Insertion...). After you have tested both, generate a very large array (30,000 or more) of bytes and sort increasingly larger portions of the array (5000, 10000, ..30000) with both algorithms. Draw a graph of execution time versus number of elements for both algorithms. What are your conclusions?

Solution

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

void heapsort(int[],int);
void heapify(int[],int);
void adjust(int[],int);
void bubble_sort(int[], int);

int main()
{
    int a[30000],a1[30000],a2[30000];
    int i,n;
    clock_t t,t2;
    printf(\"Enter size of array: \");
    scanf(\"%d\",&n);
    for(i=0;i<n;i++)
    a[i]=rand()% 100 + 1;
    for(i=0;i<n;i++)
    {
        a1[i]=a[i];
        a2[i]=a[i];
    }
    t = clock();
    heapsort(a1,n);
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
   printf(\"\ Heap sort element sorted\ \");
   printf(\"\ \");
   printf(\"Heap sort () took %f seconds to execute \ \", time_taken);
  
   t2 = clock();
   bubble_sort(a2, n);
   t2 = clock() - t2;
   double time_taken2 = ((double)t2)/CLOCKS_PER_SEC; // in seconds
   printf(\"\ Bubble sort element sorted\ \");
   printf(\"\ \");
   printf(\"Bubble sort () took %f seconds to execute \ \", time_taken2);
    return 0;
}

void heapsort(int a[],int n) {
   int i,t;
   heapify(a,n);
   for (i=n-1;i>0;i--) {
       t = a[0];
       a[0] = a[i];
       a[i] = t;
       adjust(a,i);
   }
}
void heapify(int a[],int n) {
   int k,i,j,item;
   for (k=1;k<n;k++) {
       item = a[k];
       i = k;
       j = (i-1)/2;
       while((i>0)&&(item>a[j])) {
           a[i] = a[j];
           i = j;
           j = (i-1)/2;
       }
       a[i] = item;
   }
}
void adjust(int a[],int n) {
   int i,j,item;
   j = 0;
   item = a[j];
   i = 2*j+1;
   while(i<=n-1) {
       if(i+1 <= n-1)
           if(a[i] <a[i+1])
            i++;
       if(item<a[i]) {
           a[j] = a[i];
           j = i;
           i = 2*j+1;
       } else
           break;
   }
   a[j] = item;
}
void bubble_sort(int iarr[], int num)
{
   int i, j, k, temp;
   for (i = 1; i < num; i++)
   {
      for (j = 0; j < num - 1; j++)
      {
         if (iarr[j] > iarr[j + 1])
         {
            temp = iarr[j];
            iarr[j] = iarr[j + 1];
            iarr[j + 1] = temp;
         }
      }
   }
}

                  number of elements                  Time taken
Heap Sort               5000                                                  0.001991secs
Bubble Sort             5000                                                  0.148994secs
Heap Sort               10000                                                 0.004196secs
Bubble Sort             10000                                                 0.496741secs
Heap Sort               20000                                                  0.008796secs
Bubble Sort             20000                                                 0.929185secs
Heap Sort               30000                                                 0.012187secs
Bubble Sort             30000                                                  4.543961secs

from this table we can calulate that heap sort is much faster than bubble sort