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:

- private int partition(T[] array, int lo, int hi, int pivotIndex)
- {
- T pivotValue = array[ pivotIndex ];
- swap(array, pivotIndex, hi); //send pivot item to the back
- int index = lo; //keep track of where the front ends
- for (int i = lo; i < hi; i++) //check from the front to the back
- {
- //swap if the current value is less than the pivot
- if ( (array[i]).compareTo(pivotValue) <= 0 )
- {
- swap(array, i, index);
- index++;
- }
- }
- swap(array, hi, index); //put pivot item in the middle
- return index;
- }

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.

- private T[] quicksort(T[] array, int lo, int hi)
- {
- if (hi > lo)
- {
- int partitionPivotIndex = lo;
- int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
- quicksort(array, lo, newPivotIndex-1);
- quicksort(array, newPivotIndex+1, hi);
- }
- return (T[]) array;
- }

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 <code>quicksort(array, lo, newPivotIndex-1);</code> and the entire array minus the pivot is passed into

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

- private T[] quicksort(T[] array, int lo, int hi)
- {
- if (hi > lo)
- {
- int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
- quicksort(array, lo, newPivotIndex-1);
- quicksort(array, newPivotIndex+1, hi);
- }
- return (T[]) array;
- }

- public class QuickSort<T extends Comparable<T>>
- {
- public void sort(T[] array)
- {
- array = quicksort(array, 0, array.length-1);
- }
- private T[] quicksort(T[] array, int lo, int hi)
- {
- if (hi > lo)
- {
- int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
- quicksort(array, lo, newPivotIndex-1);
- quicksort(array, newPivotIndex+1, hi);
- }
- return (T[]) array;
- }
- private int partition(T[] array, int lo, int hi, int pivotIndex)
- {
- T pivotValue = array[ pivotIndex ];
- swap(array, pivotIndex, hi); //send to the back
- int index = lo;
- for (int i = lo; i < hi; i++)
- {
- if ( (array[i]).compareTo(pivotValue) <= 0 )
- {
- swap(array, i, index);
- index++;
- }
- }
- swap(array, hi, index);
- return index;
- }
- private void swap(T[] array, int i, int j)
- {
- T temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- }Reference: http://www.geekpedia.com/tutorial290_Quicksort-in-Java.html