Analysis of Heap Sort

Best Case

Enter 5 numbers

Sorted Array:

No. of instructions count:

Enter 10 numbers

Sorted Array:

No. of instructions count:

Enter 15 numbers

Sorted Array:

No. of instructions count:

Enter 20 numbers

Sorted Array:

No. of instructions count:

Enter 25 numbers

Sorted Array:

No. of instructions count:

Average Case

Enter 5 numbers

Sorted Array:

No. of instructions count:

Enter 10 numbers

Sorted Array:

No. of instructions count:

Enter 15 numbers

Sorted Array:

No. of instructions count:

Enter 20 numbers

Sorted Array:

No. of instructions count:

Enter 25 numbers

Sorted Array:

No. of instructions count:

Worst Case

Enter 5 numbers

Sorted Array:

No. of instructions count:

Enter 10 numbers

Sorted Array:

No. of instructions count:

Enter 15 numbers

Sorted Array:

No. of instructions count:

Enter 20 numbers

Sorted Array:

No. of instructions count:

Enter 25 numbers

Sorted Array:

No. of instructions count:

Algorithm
  
 
1.	 Heapify(A as array, n as int, i as int)
2.	    max = i
3.	    leftchild = 2i + 1
4.	    rightchild = 2i + 2
5.	    if (leftchild <= n) and (A[i] < A[leftchild])
6.	        max = leftchild
7.	    else 
8.	        max = i
9.	    if (rightchild <= n) and (A[max]  > A[rightchild])
10.	        max = rightchild
11.	    if (max != i)
12.	        swap(A[i], A[max])
13.	        Heapify(A, n, max)

14.	   Heapsort(A as array) 
15.	   n = length(A)
16.	   for i = n/2 downto 1   
17.	     Heapify(A, n ,i)
18.	   for i = n downto 2
19.	     exchange A[1] with A[i]
20.	     A.heapsize = A.heapsize - 1
21.	     Heapify(A, i, 0)

  
Program
  
#include <stdio.h>
int count=0;
void max_heapify(int *,int);
void build_max_heap(int *,int);
void heapsort(int *,int);
void swap(int *,int *);
int heapsize;
void main()
    {
	    void getdata(int[],int);
	    void putdata(int[],int);
	    int *arr,n,i;
	    clrscr();
	    printf("Enter size of array=");
	    scanf("%d",&n);
	    arr=(int *)malloc(sizeof(int)*n);
	    getdata(arr,n);
	    printf("\nUnsorted array=");
	    putdata(arr,n);

	    
	    heapsort(arr,n);
	    printf("\nSorted array=");
	    putdata(arr,n);
	    printf("\nCount=%d",count);

	    getch();
    }

void heapsort(int *arr,int len)
 {
   
	int i;
   count++;
   build_max_heap(arr,len);
     count++;
    for(i= len-1;i>=1;i--)
    {
	 count++;
	swap(&arr[0],&arr[i]);
	 count++;
	heapsize = heapsize -1;
	 count++;
	max_heapify(arr,0);
	 count++;
    }
 }
void max_heapify(int *arr,int i)
{
    int l=2*i,r=2*i+1,largest;
    count++;
    if(l<heapsize && arr[l]>arr[i])
	 {
		count++;
		largest = l;
		count++;
	 }
	else
	{
		count++;
		largest = i;
		count++;
	}
	  count++;
    if(r < heapsize && arr[r]>arr[largest])
    {
		count++;
		largest = r;
		count++;
    }
     count++;
    if(largest != i)
    {
		count++;
		swap(&arr[i],&arr[largest]);
		count++;
		max_heapify(arr,largest);
		count++;
    }
}
void build_max_heap(int *arr,int len)
{
    heapsize = len;
    int i;
    count++;
    for(i =len/2;i>=0;i--)
    {
	count++;
	max_heapify(arr,i);
	count++;
    }
}
void swap(int *a ,int *b)
{
    int temp = *a;
    *a= *b;
    *b= temp;
}

void getdata(int x[10],int n)
{
     int k;
     printf("\nEnter the %d elements for sorting=\n",n);
     for(k=0;k<n;k++)
     {
      scanf( "%d" ,&x[k]);
     }
}
void putdata(int x[10], int n)
{
	int k;
	for(k=0;k < n;k++)
	{
	      printf( "%d" ,x[k]);
	}
	 printf("\n");
}

	    
Best Case
Average Case
Worst Case
5 Numbers
10 Numbers
15 Numbers
20 Numbers
25 Numbers

select appropriate function for growth of graph

Best case
Average case
Worst case