Thursday, June 17, 2010

QuickSort in Java

This post is a part of my continuous effort to just implement few of the important data structures in Java. Please find my previous post on LinkedList. Probably I just want to pay back, those bunking college days.... :-) Anyway, whatever be the case I'm really enjoying doing this.....
 
Let’s start with the output-

Array to sort: [80, 30, 10, 5, 7, 40, 0]
Mid: 3
Pivot: 5
Left Array: [5, 0]
Right Array: [80, 30, 10, 7, 40]
Mid: 1
Pivot: 0
Left Array: [0]
Right Array: [5]
Inter list: (can u see that ? it's getting better)
0 5
Mid: 2
Pivot: 10
Left Array: [10, 7]
Right Array: [80, 30, 40]
Mid: 1
Pivot: 7
Left Array: [7]
Right Array: [10]
Inter list: (can u see that ? it's getting better)
7 10
Mid: 1
Pivot: 30
Left Array: [30]
Right Array: [80, 40]
Mid: 1
Pivot: 40
Left Array: [40]
Right Array: [80]
Inter list: (can u see that ? it's getting better)
40 80
Inter list: (can u see that ? it's getting better)
30 40 80
Inter list: (can u see that ? it's getting better)
7 10 30 40 80
Inter list: (can u see that ? it's getting better)
0 5 7 10 30 40 80
Huh...I'm done. It's quite a logic.
Sorted Array: [0 5 7 10 30 40 80 ]

partition(int[] list)divides the list and sort it. So to sort any array of randomly ordered elements, pass the unsorted array to this method and it will return back the sorted array.

/**
 * It is a recursive function which will make partition and sort.
 *
 * @param list- unsorted list
 * @return
 */
public int[] partition(int[] list){
           
            if(list.length == 1 || list.length == 0){
                  /*
                   * Only one element in the list or no element. 
                   * Come on! You are  still testing me?
                   */
                  return list;
            }
           
            /*
             * Get the mid position of the list and consider that as the
             * Pivot element
             */
            int mid = list.length/2;
            int pivot = list[mid];
            System.out.println("Mid: "+ mid);
            System.out.println("Pivot: "+ pivot);
            /*
             * Use some dynamic structure, as you still don't know how many can
             * come in the Left and Right partition. I guess ArrayList will be  
             * good as you can quickly get the Array back...
             */
            ArrayList leftList = new ArrayList();
            ArrayList rightList = new ArrayList();
           
            for(int i=0; ilength; i++){
                  if(list[i] <= pivot){
                        /*
                         * Put all smaller and equals in the Left Partition
                         */
                        leftList.add(new Integer(list[i]));
                  }
                  else
                        /*
                         * This is for big boys...all values greater than Pivot
                         */
                        rightList.add(new Integer(list[i]));
            }
           
            System.out.println("Left Array: "+ leftList);
            System.out.println("right Array: "+ rightList);
           
            /*
             * Return back my arrays.
             * Create the arrays which will keep the recursive processing rational
             */
            int[] leftArray = new int[leftList.size()];
            int[] rightArray = new int[rightList.size()];
           
            for(int i=0; i
                  leftArray[i] = leftList.get(i).intValue();
            for(int i=0; i
                  rightArray[i] = rightList.get(i).intValue();
           
            /*
             * Repeat the same logic with Left and Right partition
             */
            leftArray = partition(leftArray);
            rightArray = partition(rightArray);

            int li = 0;
            int ri = 0;
           
            /*
             * As the individual partitions get sorted, put them back in the
             * main list
             */
            for(int i=0; i<list.length; i++){
                  if(li < leftArray.length){
                        list[i] = leftArray[li++];
                        continue;
                  }
                  if(ri < rightArray.length){
                        list[i] = rightArray[ri++];
                  }
            }
            /*
             * You can check how the sorting is progressing in 
             * intermediate  stages-
             */
            System.out.println("Inter list:(can u see that? it's getting better) ");
            int x = 0;
            while(x < list.length)
                  System.out.print(list[x++]+" ");
            System.out.println();
           
            return list;
} 

Please feel free to share any error cases in the above implementation.

 

No comments:

Post a Comment