Quicksort

This shows an implementation of Quicksort as described at en.wikipedia.org. This algorithm has average runtime of O(n log n). This is because the pivot is compared to each element in the partition which is O(n) comparisons. Also, the divide and conquer methodology causes log n partitions to be created.

--------

---|-----

-|--|---|--

 |-|-|--|-|-|-

      -|-

package algorithm;

public class quicksort {
 public static void main(String[] args) {
  System.out.println("Case I");
  int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  quicksort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
  
  System.out.println("Case II");
  numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  quicksort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case III");
  numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  quicksort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case IV");
  numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  quicksort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
 }

 private static void printArray(int start, int end, int[] numbers, String text) {
  String out = "{";
  String del = "";
  for(int i=start; i < end + 1; i++) {
   out = out + del + numbers[i] + "";
   del = ",";
  }
  out = out + "}";
  System.out.println(text+":"+out);
 }
 
 // O(n log n)
 private static int[] quicksort(int[] numbers) {
  int start = 0;
  int end = numbers.length - 1;
  
  // O(log n) on outer loop - recursion - O(log n) number of partitions
  partitionpivot(start, end, numbers);
  return numbers;
 }

 private static void partitionpivot(int start, int end, int[] numbers) {
  int walker = start;
  int pivot = end;
  if(start >= end) {
   return;
  }
  
  int pivotnumber = numbers[pivot];

  // O(n) on inner loop
  while(walker < pivot) {
   int walkernumber = numbers[walker];
   if(walkernumber > pivotnumber) {
    swapWalkerPivotAndNotProcessedNumber(numbers, walker, walkernumber, pivot, pivotnumber);
    printArray(start, end, numbers, "pivot_move");
    pivot--;
   } else {
    walker++;
   }
  }

  // O(log n) on outer loop - recursion - O(log n) number of partitions
  partitionpivot(0, pivot - 1, numbers);
  partitionpivot(pivot + 1, end, numbers);
 }

 private static void swapWalkerPivotAndNotProcessedNumber(int[] numbers,
   int walker, int walkernumber, int pivot, int pivotnumber) {
  numbers[pivot] = walkernumber;
  numbers[walker] = numbers[pivot - 1]; // when walker == pivot - 1, this does nothing
  numbers[pivot - 1] = pivotnumber;
 }
}

Output

Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
pivot_move:{3,5,8,5,2,1,9,4,7}
pivot_move:{3,9,8,5,2,1,4,5,7}
pivot_move:{3,1,8,5,2,4,9,5,7}
pivot_move:{3,1,2,5,4,8,9,5,7}
pivot_move:{3,1,2,4,5,8,9,5,7}
pivot_move:{1,2,3}
pivot_move:{5,5,9,7,8}
pivot_move:{5,5,7,9,8}
pivot_move:{8,9}
post_sort:{1,2,3,4,5,5,7,8,9}
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
pivot_move:{2,8,7,6,5,4,3,1,9}
pivot_move:{3,8,7,6,5,4,1,2,9}
pivot_move:{4,8,7,6,5,1,3,2,9}
pivot_move:{5,8,7,6,1,4,3,2,9}
pivot_move:{6,8,7,1,5,4,3,2,9}
pivot_move:{7,8,1,6,5,4,3,2,9}
pivot_move:{8,1,7,6,5,4,3,2,9}
pivot_move:{1,8,7,6,5,4,3,2,9}
pivot_move:{1,3,7,6,5,4,2,8}
pivot_move:{1,4,7,6,5,2,3,8}
pivot_move:{1,5,7,6,2,4,3,8}
pivot_move:{1,6,7,2,5,4,3,8}
pivot_move:{1,7,2,6,5,4,3,8}
pivot_move:{1,2,7,6,5,4,3,8}
pivot_move:{1,2,4,6,5,3,7}
pivot_move:{1,2,5,6,3,4,7}
pivot_move:{1,2,6,3,5,4,7}
pivot_move:{1,2,3,6,5,4,7}
pivot_move:{1,2,3,5,4,6}
pivot_move:{1,2,3,4,5,6}
post_sort:{1,2,3,4,5,6,7,8,9}
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
post_sort:{5,5,5,5,5,5,5,5,5}
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}