Friday, September 6, 2013

QuickSort on an Array

Implement a QuickSort on an Array


public class QuickSort {
   
    int partition( int[] in ) {
        if ( in.length == 1) return 0;
   
        if ( in.length == 2 ) {
            if ( in[0] > in[1]) {
                swap(in , 0 ,1);
                return 1;
            }else if( in[0] == in[1])
                return 1;
            else return 0;
               
        }
       
        int pivot = in[0];
        int down = 1;
        int up = in.length - 1;
        int ele = -1;
       
        while ( up > down ) {
            // move down pointer
            while( in[down] <= pivot && down < in.length -1)
                ++down;
                   
            while( in[up] > pivot && up > 0)
                --up;
               
            if ( up > down) {
                swap(in, down, up);
                ele = down;
               
                ++down;
                --up;
            }
        }

        if ( in[up] > pivot) {
            swap(in, 0, ele);
        }else{
            swap(in, 0, up);
            ele = up;
        }

        return ele;
    }
   
    private void swap( int[] in, int lb, int ub ) {
        int tmp = in[lb];
        in[lb] = in[ub];
        in[ub] = tmp;
    }
   
    void print(int[] in) {
        for( int i: in )
            System.out.println(i);
    }
   
    public static void main( String[] args ) {
       
        int[] in = new int[] {57,25, 36, 69, 22, 99, 48, 98, 88, 79, 62 };
       
        int[] in1 = new int[] {25, 22, 21, 23, 24 };
       
        int[] in2 = new int[] { 21, 24, 26, 28, 49 };
       
        int[] in3 = new int[] { 25, 57, 48, 37, 12, 92, 86, 33};
       
        int[] in4 = new int[]{2,1,3,-2,0};
       
        int[] in5 = new int[]{2,1,0,6,-7};
       
        int[] in6 = new int[]{25,35,49,50,21,22,25};
       
        int[] in7 = new int[]  {2,1,2};
       
        int[] in8 = new int[]  {2,2};
       
        QuickSort sort = new QuickSort();
   
        System.out.println("--------------------");
       
        System.out.println(sort.partition(in));
        sort.print(in);
       
        System.out.println("-------------------------------");
        System.out.println(sort.partition(in1));
        sort.print(in1);
   
        System.out.println("-------------------------");
        System.out.println(sort.partition(in2));
        sort.print(in2);
       
        System.out.println("-------------------------------");
        System.out.println(sort.partition(in3));
        sort.print(in3);
       
        System.out.println("-------------------------------");
        System.out.println(sort.partition(in4));
        sort.print(in4);
       
        System.out.println("----------------------");
        System.out.println(sort.partition(in5));
        sort.print(in5);
       
        System.out.println("-------------------------");
        System.out.println(sort.partition(in6));
        sort.print(in6);
       
        System.out.println("---------------------------");
        System.out.println(sort.partition(in7));
        sort.print(in7);
       
        System.out.println("---------------------------");
        System.out.println(sort.partition(in8));
        sort.print(in8);
       
       
    }

}


No comments:

Post a Comment