### Quicksort in Java

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:

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

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.

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...

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