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, the list is divided into two sublists - the first sublist containing all values less than or equal to the pivot and the second sublist 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). The algorithm selects the first element of the array as pivot value, but you can choose any value as the 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 the 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 a stack to eliminate recursion.
• On a small array, Insertion Sort is faster than Quicksort. So you can consider using Insertion sort if the size of the array is small. 

References

http://algs4.cs.princeton.edu/23quicksort/

--
keep coding !!!