Sunday, April 6, 2014

Quicksort Implementation

Quicksort is a divide-and-conquer algorithm which centers around efficiently choosing the pivot value from the input data set. Based on this pivot value, list is divided into two sub lists - first sub list containing all values less than or equal to the pivot and second sub list containing all values greater than the pivot. This procedure is recursively called on these two sub lists.

Wikipedia has an interesting animation.

Below algorithm sorts array in-place and without using any extra space ( except the temporary holder, tmp). Algorithm selects first element of the array as pivot value, but you can chose any value as pivot.

Java Implementation 


package algo;

/**
 * QuickSort implemention
 * 
 * @author Siddheshwar
 * 
 */
public class QuickSort {

 /**
  * This method actually partitions the array in two sub parts. Doing
  * recursively the same, sorts the array as well
  * 
  */
 static int[] partition(int[] a, int low, int high) {
  int pi = low;
  int pivot = a[pi];
  int i = low, j = high;

  while (i < j) {
   // i should not exceed the high bound
   while (a[i] <= pivot && i < high)
    i++;

   // j should not reduce below low bound
   while (a[j] > pivot && j >= i)
    j--;

   if (i < j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
   }
  }

  // j is the final position for pivot element
  int tmp = a[j];
  a[j] = pivot;
  a[pi] = tmp;
  pi = j;

  // just for testing
  logging(a, pi);

  // do the same for lower and higher sub arrays
  if (low < pi - 1) {
   partition(a, low, pi - 1);
  }
  if (pi + 1 < high) {
   partition(a, pi + 1, high);
  }

  return a;
 }

 /**
  * Print array after each iteration to see how this sort works
  * 
  */
 public static void logging(int[] a, int pi) {
  for (int t : a) {
   System.out.print(t + " ");
  }
  System.out.println("\nPivot index :" + pi + "; Pivot :" + a[pi]);
 }

 public static void main(String[] args) {
  // int[] a = {0,666,1, 10, 30, 5, 19, 10};
  // int[] a = {1,1,1,1,1,1,1};
  // int[] a = {1,2,1,2,1,2,1};

  int[] a = { 0, 666, 2, 2, 2, 2, 45, 2, 3, 3, 3, 3 };
  a = QuickSort.partition(a, 0, a.length - 1);

  System.out.println("\nsorted array");
  for (int t : a) {
   System.out.print(t + " ");
  }
 }
}

Output:
0 666 2 2 2 2 45 2 3 3 3 3
Pivot index :0; Pivot :0
0 3 2 2 2 2 45 2 3 3 3 666
Pivot index :11; Pivot :666
0 3 2 2 2 2 3 2 3 3 45 666
Pivot index :9; Pivot :3
0 3 2 2 2 2 3 2 3 3 45 666
Pivot index :8; Pivot :3
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :7; Pivot :3
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :5; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :4; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :3; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :2; Pivot :2

sorted array
0 2 2 2 2 2 3 3 3 3 45 666 


Important points

  • Performance of algorithm depends a lot on the choice of pivot value. If it divides the array in two almost equal sized array, run time complexity will be O(n log n). Worst case complexity for Quicksort is O(n^2).
  • It also takes O(log n) stack space on an average.
  • You can also consider using stack to eliminate recursion.
  • On small array , Insertion Sort is faster than Quick sort. So you can consider using Insertion sort if the size of the array is small. 

References

No comments:

Post a Comment