Friday, April 15, 2011

Non-Recursive Quick Sort

import java.util.*;
import java.util.Stack;
class QuickSortNonRec
{
    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 a, down, temp, up,pj;
        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 Quick(int[] a, int lb, int ub)
    {
        Stack S = new Stack();
        S.push(lb);
        S.push(ub);
        while (!S.empty())
        {
            ub = (Integer)S.pop();
            lb = (Integer)S.pop();
            if (ub <= lb) continue;
            int i = Partition(a, lb, ub);
            if (i-lb > ub-i)
            {
                S.push(lb);
                S.push(i-1);
            }
            S.push(i+1);
            S.push(ub);
            if (ub-i >= i-lb)
            {
                S.push(lb);
                S.push(i-1);
            }
        }
    }

    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 10 numbers");
        for(i=0;i<n;i++)
            x[i] = in.nextInt();
        Quick(x,0,n-1);
        System.out.println("\nSorted Elements are :");
        for(i=0;i<n;i++)
            System.out.print(x[i] + "  ");
    }
}