Heapsort

Heapsort is a sorting technique that sorts a contiguous list of length n with O(n log2 (n)) comparisons and movement of entries, even in the worst case. Hence it achieves the worst-case bounds better than those of quick sort, and for the contiguous list, it is better than merge sort, since it needs only a small and constant amount of space apart from the list being sorted.
Heapsort proceeds in two phases. First, all the entries in the list are arranged to satisfy the heap property, and then the top of the heap is removed and another entry is promoted to take its place repeatedly. Therefore, we need a function that builds an initial heap to arrange all the entries in the list to satisfy the heap property. The function that builds an initial heap uses a function that adjusts the ith entry in the list, whose entries at 2i and 2i + 1 positions already satisfy the heap property in such a manner that the entry at the ith position in the list will also satisfy the heap property.

Example

#include <stdio.h>
#define MAX 10
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

void adjust( int list[],int i, int n)
{
   int j,k,flag;
   k = list[i];
   flag = 1;
   j = 2 * i;
   while(j <= n && flag)
   {
      if(j < n && list[j] < list[j+1])
      j++;
      if( k >= list[j])
               flag =0;
      else
      {
         list[j/2] = list[j];
         j = j *2;
      }
   }
   list [j/2] = k;
}

void build_initial_heap( int list[], int n)
{
   int i;
   for(i=(n/2);i>=0;i--)
       adjust(list,i,n-1);
}

void heapsort(int list[],int n)
{
   int i;
   build_initial_heap(list,n);
   for(i=(n-2); i>=0;i--)
   {
      swap(&list[0],&list[i+1]);
      adjust(list,0,i);
   }
}

void readlist(int list[],int n)
{
   int i;
   printf("Enter the elements\n");
   for(i=0;i<n;i++)
       scanf("%d",&list[i]);
}

void printlist(int list[],int n)
{
   int i;
   printf("The elements of the list are: \n");
   for(i=0;i<n;i++)
       printf("%d\t",list[i]);
}

int main()
{
   int list[MAX], n;
   printf("Enter the number of elements in the list max = 10\n");
   scanf("%d",&n);
   readlist(list,n);
   printf("The list before sorting is:\n");
   printlist(list,n);
   heapsort(list,n);
   printf("The list after sorting is:\n");
   printlist(list,n);
   getchar();
   return 0;
}

Explanation

In each pass of the while loop in the function adjust(x, i, n), the position i is doubled, so the number of passes cannot exceed log( n/i). Therefore, the computation time of adjust is O(log n/i).
The function build_initial_heap calls the adjust procedure n/2 for values ranging from n1/2 to 0. Hence the total number of iterations will be:

This turns out to be some constant time n. So the computation time of build_initial_heap is O(n). The heapsort function calls the adjust (x,1, i) (n−1) times. So the total number of iterations made in the heapsort will be

which turns out to be approximately n log(n). So the computing time of heapsort is O(n log(n)) + O(n). The only additional space needed by heapsort is the space for one record to carry out the exchange.