...
Which value to use as the pivot? Consider this: on average, for any randomly chosen element in the set (array), the value of that element is the mean of all the values. Thus, on average, half of the values in the set are smaller than any randomly chosen value and half are thus larger. What does this all mean? It means that it doesn't matter which element we choose to be our pivot because on average, half of the values will be larger than our pivot and half will be smaller, which is what we want. So, why not pick the first element? It's statistically no different than any other elenent and its real easy to find!
Here's a very basic implementation of Quicksort in an imperative coding style:
| Code Block |
|---|
import java.util.*;
class QuicksortBasic implements QuickSort {
public ArrayList<Integer> sort(ArrayList<Integer> a) {
if (a.isEmpty()) return new ArrayList<Integer>();
ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> mid = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();
for (Integer i : a)
if ( i < a.get(0) )
left.add(i); // Use element 0 as pivot
else if ( i > a.get(0))
right.add(i);
else
mid.add(i);
ArrayList<Integer> left_s = sort(left);
ArrayList<Integer> right_s = sort(right);
left_s.addAll(mid);
left_s.addAll(right_s);
return left_s;
}
}
|
...
It is possible to optimize this code further to make it even faster.
From an OO sorting perspective, Quicksort is a hard-split, easy join example of Merritt's sorting theorem.
| Code Block |
|---|
/**
* A concrete sorter that uses the QuickSort method.
*/
public class QuickSorter extends ASorter
{
/**
* The constructor for this class.
* @param iCompareOp The comparison strategy to use in the sorting.
*/
public QuickSorter(AOrder iCompareOp)
{
super(iCompareOp);
}
/**
* Splits A[lo:hi] into A[lo:s-1] and A[s:hi] where s is the returned value of this function.
* This method places all values greater than the key at A[0] at indices above the split index
* and all values below the key at indices less than the split index.
* @param A the array A[lo:hi] to be sorted.
* @param lo the low index of A.
* @param hi the high index of A.
* @return The split index.
*/
protected int split(Object[] A, int lo, int hi)
{
Object key = A[lo];
int lx = lo; // left index.
int rx = hi; // right index.
// Invariant 1: key <= A[rx+1:hi].
// Invariant 2: A[lo:lx-1] <= key.
// Invariant 3: there exists ix in [lo:rx] such that A[ix] <= key.
// Invariant 4: there exists jx in [lx:hi] such that key <= A[jx].
while (lx <= rx)
{
while (aOrder.lt(key, A[rx])) // will terminate due to invariant 3.
{
rx--; // Invariant 1 is maintained.
} // A[rx] <= key <= A[rx+1:hi]; also invariant 0, lx <= rx.
while (aOrder.lt(A[lx], key)) // will terminate due to invariant 4.
{
lx++; // Invariant 2 is maintained.
} // A[lo:lx-1] <= key <= A[lx]
if (lx <= rx)
{
// swap A[lx] with A[rx]:
Object temp = A[lx];
A[lx] = A[rx]; // invariant 3 is maintained.
A[rx] = temp; // invariant 4 is maintained.
rx--; // invariant 1 is maintained.
lx++; // invariant 2 is maintained.
}
} // rx < lx, A[lo:lx-1] <= key <= A[rx+1:hi], and key = A[lx].
return lx;
}
/**
* Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
* This method does nothing, as the sub-arrays are already in proper order.
* @param A A[lo:s-1] and A[s:hi] are sorted.
* @param lo the low index of A.
* @param s
* @param hi the high index of A.
*/
protected void join(Object[] A, int lo, int s, int hi)
{
}
}
|
Also download the lecture notes on this subject.
...