Saturday, 9 August 2014

Heap Sort

This is the implementation of heap sort using the C programming language. If you have any doubts, please let me know.

#include<stdio.h>
int tree[50],n=0;
void del();
void ins(int);
main()
{
            int x,i,a;
            printf("\nEnter the number of elements:");
            scanf("%d",&a);
            printf("\nEnter the elements:");
            for(i=0;i<a;i++)
            {
                        scanf("%d",&x);
                        ins(x);
            }
            printf("\nAfter Sorting:\n");
            del();   
}

void ins(int x)
{
            int ptr,par;
            n=n+1;
            ptr=n;
            while(ptr>1)
            {
                        par=ptr/2;
                        if(x<=tree[par])
                        {
                                    tree[ptr]=x;
                                    return;
                        }
                        tree[ptr]=tree[par];
                        ptr=par;
            }
            tree[1]=x;
            return;
}

void del()
{
            int i,x,ptr,last,left,right;
            while(n!=0)
            {
                        x=tree[1];
                        printf(" %d  ",x);
                        last=tree[n];
                        n=n-1;
                        ptr=1;
                        left=2;
                        right=3;
                        while(right<=n)
                        {
                                    if(last>=tree[left]&&last>=tree[right])
                                    {
                                                tree[ptr]=last;
                                                break;
                                    }
                                    else if(tree[right]<=tree[left])
                                    {
                                                tree[ptr]=tree[left];
                                                ptr=left;
                                    }
                                    else
                                    {
                                                tree[ptr]=tree[right];
                                                ptr=right;
                                    }
                                    left=2*ptr;
                                    right=left+1;
                        }
                        if((left==n)&&(last<tree[left]))
                        {
                                    tree[ptr]=tree[left];
                                    ptr=left;
                        }
                        tree[ptr]=last;
}
            return;
}



No comments:

Post a Comment