Thursday, November 21, 2013

HeapSort C Program (DFS)

#include<stdio.h>
#include<conio.h>

void build_Heap(int [],int);
void HeapSort(int H[],int n);

int main()
{
    int arr[10],n,i;
    printf("Enter the total number of array elements: ");
    scanf("%d",&n);

    
    printf("Enter the array elements: ");
    for(i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    
    HeapSort(arr,n);
    
    printf("The sorted array is: ");
    for(i=1;i<=n;i++)
    {
        printf("\t%d",arr[i]);
    }
    
    getch();
    return 0;
}

void build_Heap(int H[],int n)
{
    int i,j,k,v,heap;
    for(i=n/2;i>=1;i--)
    {
        k=i;
        v=H[k];
        heap=0;
        while(heap==0 && (2*k)<=n)
        {
            j=2*k;
            if(j<n)
            {
                if(H[j]<H[j+1])
                    j++;
            }
            if(v>=H[j])
                heap=1;
            else
            {
                H[k]=H[j];
                k=j;
            }
        }
        H[k]=v;
    }
}

void HeapSort(int H[],int n)
{
    int t,i;
    for(i=n;i>=1;i--)
    {
        build_Heap(H,i);
        t=H[1];
        H[1]=H[i];
        H[i]=t;
    }
}

No comments:

Post a Comment