Friday, April 15, 2011

Recursive Quick Sort

ava.util.Scanner;
class QuickSortRec
{
    static void Display(int x[], int n)
    {
        int i;
        System.out.println(" ");
        for(i=0;i<n;i++)
            System.out.print("\t"+x[i]+ " ");
        System.out.println(" ");
    }
   
    static int Partition(int x[], int lb, int ub, int pj)
    {
        int a, down, temp, up;
        a=x[lb];
        up=ub;
        down=lb;
        while(down<up)
        {
            while(x[down]<=a && down<up)
                down=down+1;
            while(x[up]>a)

                up=up-1;
            if(down<up)
            {
                temp=x[down];
                x[down]=x[up];
                x[up]=temp;
            }
        }
        x[lb]=x[up];
        x[up]=a;
        pj=up;
        return (pj);
    }

    static void Quicksort(int x[], int lb, int ub, int n)
    {
        int j=0;
        if(lb>=ub)
            return;
        j=Partition(x, lb, ub, j);
        System.out.println("After partitioning array from index "+(lb+1)+" to "+(ub+1)+ " :\n ");
        Display(x,n);
        Quicksort(x, lb, j-1, n);
        Quicksort(x, j+1, ub, n);
    }

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