Heap Sort

Problem statement
Write a c program to sort numbers using heap sort(using max heap)
#include<stdio.h>
#include<stdlib.h>
void manage(int *, int);
void adjust(int *, int, int);
int delete(int a[],int start,int size);
int main()
{
 int i,j,size,tmp,k,*arr;
 printf("\n\t------- Heap sorting method -------\n\n");
 printf("Enter the number of elements to sort : ");
 scanf("%d",&size);
 arr=(int *)malloc((size+1)*sizeof(int));
 for(i=1; i<=size; i++)
 {
   printf("Enter %d element : ",i);
   scanf("%d",&arr[i]);
   manage(arr,i);
 }
 j=size;
 for(i=1; i<=j; i++)
 {
   arr[size]=delete(arr,1,size);
   size--;
}
 printf("\n\t------- Heap sorted elements -------\n\n");
 for(i=1; i<=j; i++)
     printf("%d ",arr[i]);

 return 0;
}
int delete(int a[],int start,int size)
{
    int temp;
    if(size<1)
    {
        printf("no element in the array ");
        return -1;
    }
    printf("element %d deleted \n",a[start]);
    temp=a[start];
    a[start]=a[size];                         // removing the first element
    adjust(a,start,size-1);                 //adjusting the tree
    return temp;
}


void adjust(int *arr, int i, int size)
{
 int tmp,j;
 tmp=arr[i];
 j=i*2;
 while(j<=size)
 {
   if((j<size)&&(arr[j]<arr[j+1]))
      j++;
   if(arr[j]<arr[j/2])
      break;
   arr[j/2]=arr[j];
   j=j*2;
 }
 arr[j/2]=tmp;
 return ;
}


void manage(int *arr, int i)
{
 int tmp;
 tmp=arr[i];
 while((i>1)&&(arr[i/2]<tmp))
 {
   arr[i]=arr[i/2];
   i=i/2;
 }
 arr[i]=tmp;
 return ;
}

1 comment: