Friday, April 15, 2011

Heap Sort


import java.util.Scanner;
class HeapSort
{
    static void Display(int a[], int n)
    {
        int i;
        for(i=0;i<n;i++)
            System.out.print("   "+a[i]);
        System.out.println("\n---------------------------------");
    }

    static void Heap(int x[],int n)
    {
        int i,elt,s,f,ivalue,pass=1;
        for(i=1;i<n;i++)
        {
            elt=x[i];
            s=i;
            f=(s-1)/2;
            while((s>0)&&(x[f]<elt))
            {
                x[s]=x[f];
                s=f;
                f=(s-1)/2;
            }
            x[s]=elt;

        }
        for(i=n-1;i>0;i--)
        {
            ivalue=x[i];
            x[i]=x[0];
            f=0;
            if(i==1)
                s=-1;
            else
                s=1;
            if((i>2) && (x[2]>x[1]))
                s=2;
            while((s>=0)&&(ivalue<x[s]))
            {
                x[f]=x[s];
                f=s;
                s=2*f+1;
                if((s+1<=i-1)&&(x[s]<x[s+1]))
                    s=s+1;
                if(s>(i-1))
                    s=-1;
            }
            x[f]=ivalue;
            System.out.print("\tPass "+(pass++)+" : ");
            Display(x,n);
        }
    }

    public static void main(String args[ ])
    {
                int i,n=10;
        Scanner in = new Scanner(System.in);
        int x[]=new int[10];
        System.out.println("Enter numbers");
        for(i=0;i<10;i++)
            x[i] = in.nextInt();
        Heap(x,10);
        System.out.println("\nSorted Elements are :");
        for(i=0;i<n;i++)
        System.out.print(x[i] + "  ");
    }
}