2.24.2012

Heap sorting

Q. Write a C program to sort 5 numbers using heap sorting method.


Ans.


/* c program for heap sorting method*/

#include<stdio.h>
#include<conio.h>
void manage(int *int);
void heapsort(int *intint);
int main()
{
 int arr[20]; 
 int i,j,size,tmp,k;
 printf("\n\t------- Heap sorting method -------\n\n");
 printf("Enter the number of elements to sort : ");
 scanf("%d",&size);
 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++)
 {
   tmp=arr[1];
   arr[1]=arr[size];
   arr[size]=tmp;
   size--;
   heapsort(arr,1,size);
 }
 printf("\n\t------- Heap sorted elements -------\n\n");
 size=j;
 for(i=1; i<=size; i++)
     printf("%d ",arr[i]);
 getch();
 return 0;
}


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;
}


void heapsort(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;
}

/************* OUTPUT ***************/
Output of Heap sorting C program
Screen shot for Heap sorting C program

11 comments:

  1. it's nt a correct code...need some changes...

    ReplyDelete
    Replies
    1. @Gaurav
      Where you find error?
      Please mention that for improve Programming skills.

      Delete
  2. i try it using c-free in windows and there is no error, all is fine..

    if you try it with linux, try you remove #include and getch();

    Insya Allah, problem solved

    ReplyDelete
  3. thankyou very much, i will re write it again to my blog. i want to learn it more.. thankyu

    ReplyDelete
  4. ohyyaa...once i insert data = 12, there is still random, notsorted tet.. please check again, thnkyou

    ReplyDelete
  5. works only for limit below 5!!!!

    ReplyDelete
  6. if the list having repeated values then also fail

    ReplyDelete
  7. #include
    void heapsort(int heap[],int n);
    void maxheapify(int heap[],int j,int n);
    void swap(int *a,int *b);
    int main()
    {
    int n;
    scanf("%d",&n);

    int heap[n+1];
    printf("Enter the elements:\n");
    int i;
    for(i=1;i<=n;i++) scanf("%d",&heap[i]);
    heapsort(heap,n);
    return 0;
    }
    void heapsort(int heap[],int n)
    {
    int j,i,m_index;
    if(n==0)
    {
    printf("\nHeap is empty ");
    }
    else{
    j=n/2;
    for(i=j;i>0;i--){
    maxheapify(heap,i,n);}
    }

    printf("\n%d",heap[1]);
    swap(&heap[1],&heap[n]);
    n--;
    if(n>0)
    heapsort(heap,n);

    }
    void maxheapify(int heap[],int j,int n)
    {
    int l,r,m_index;
    l=2*j;
    r=2*j+1;
    if(r<=n && heap[j]<heap[r])
    {
    m_index=r;
    }
    else
    {
    m_index=j;
    }


    if(l<=n && heap[m_index]<heap[l])
    {
    m_index=l;
    }


    if(j!=m_index)
    {
    swap(&heap[j],&heap[m_index]);
    maxheapify(heap,m_index,n);
    }


    }
    void swap(int *a,int *b)
    {
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
    }

    ReplyDelete