A quick intro to the Quicksort algorithm in Java, showing an efficient (if not optimal) way to sort.

In my opinion, Quicksort is the best algorithm for sorting, when it is implemented correctly. It is the default sorting algorithm in Java itself. Of course, writing it in Java is probably not the best, but it is important to know how it works in case you need to write some variation of it for some other purpose.
The main idea is this, pick a pivot item (preferably the average of the data in the array), place all items less than and equal to the pivot item in the front of the array, all the items greater than the pivot in the back of the array and replace the pivot in the middle of the array, then recursively sort the front and back halves. The best way to do this is with a partition function that swaps values around within the array to save space. This is that function:

1. private int partition(T[] array, int lo, int hi, int pivotIndex)
2. {
3.    T pivotValue = array[ pivotIndex ];
4. 
5.    swap(array, pivotIndex, hi); //send pivot item to the back
6. 
7.    int index = lo; //keep track of where the front ends
8. 
9.    for (int i = lo; i < hi; i++) //check from the front to the back
10.   {
11.      //swap if the current value is less than the pivot
12.      if ( (array[i]).compareTo(pivotValue) <= 0 )
13.      {
14.         swap(array, i, index);
15.         index++;
16.      }
17.   }
18. 
19.   swap(array, hi, index); //put pivot item in the middle
20.
21.   return index;
22. }

This code is a little tricky to understand at first, but go through it slowly. First, we swap the pivot with the last element in the segment of the array being partitioned. Second, we set the marker index to be the front of the segment. Then the array is scanned, checking each element to see if it is less than or equal to the pivot item. If it is, the it is swapped to the front, which is where index points to and index is incremented. At the end of all that, index points to where the pivot should be replaced. If no elements were found to be less than the pivot, then the pivot should be the first element, and like wise, if all the elements were found to be less than the pivot, the pivot should be the last element. The pivot’s index is returned so that it can be used in the recursive sort step. Also, the pivot is now in it’s final place and does not need to be moved anymore.

1. private T[] quicksort(T[] array, int lo, int hi)
2. {
3.    if (hi > lo)
4.    {
5.       int partitionPivotIndex = lo;
6. 
7.       int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
8. 
9.       quicksort(array, lo, newPivotIndex-1);
10.      quicksort(array, newPivotIndex+1, hi);
11.   }
12.   return (T[]) array;
13. }

This is the actual sorting function that is called recursively. See that since the newPivotIndex points to where the pivot was, and it needs to stay there, the function is only called on the segments from lo to newPivotIndex-1 and newPivotIndex+1 to hi.
There is a problem with this code however. What happens if the array is already sorted? Go through this step by step and watch what happens. The lowest element in the segment is picked as the pivot every time. This makes the first half be just the pivot, and nothing happens with quicksort(array, lo, newPivotIndex-1); and the entire array minus the pivot is passed into

1. quicksort(array, newPivotIndex+1, hi);

It’s selection sort! That’s no good, we want to beat the O(n^2) time complexity of selection sort. Granted, this problem only occurs if the array is sorted or close to sorted, but that can happen pretty often. There are some complicated way of picking a better pivot, but I’ll just use a random number to prevent the lowest number from being picked every time.

1. private T[] quicksort(T[] array, int lo, int hi)
2. {
3.    if (hi > lo)
4.    {
5.       int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
6.       int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
7.       quicksort(array, lo, newPivotIndex-1);
8.       quicksort(array, newPivotIndex+1, hi);
9.    }
10.   return (T[]) array;
11. }

With a random number, there is no guarantee that it still won’t “go quadratic”, but the chances are greatly reduced since the expected value of the random number is the average of hi and lo, and the expected value of the number at that index in an already (or close to) sorted array is the average of that array. If the average value of the array is picked as the pivot, then about half of the array is passed into each recursive call. If half of the array is passed into each call then the time complexity of the algorithm becomes O(nlogn) since the partition portion takes O(n) time and half of the array is recursed on with O(logn) time, which is much better for large values of n. So putting it all together…

1. public class QuickSort<T extends Comparable<T>>
2. {
3.    public void sort(T[] array)
4.    {
5.       array = quicksort(array, 0, array.length-1);
6.    }
7. 
8.    private T[] quicksort(T[] array, int lo, int hi)
9.    {
10.      if (hi > lo)
11.      {
12.         int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
13.         int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
14.         quicksort(array, lo, newPivotIndex-1);
15.         quicksort(array, newPivotIndex+1, hi);
16.      }
17.      return (T[]) array;
18.   }
19.
20.   private int partition(T[] array, int lo, int hi, int pivotIndex)
21.   {
22.      T pivotValue = array[ pivotIndex ];
23.
24.      swap(array, pivotIndex, hi); //send to the back
25.
26.      int index = lo;
27. 
28.      for (int i = lo; i < hi; i++)
29.      {
30.         if ( (array[i]).compareTo(pivotValue) <= 0 )
31.         {
32.            swap(array, i, index);
33.            index++;
34.         }
35.      }
36.
37.      swap(array, hi, index);
38.
39.      return index;
40.   }
41. 
42.   private void swap(T[] array, int i, int j)
43.   {
44.      T temp = array[i];
45.      array[i] = array[j];
46.      array[j] = temp;
47.   }
48.
49. }