Quicksort
Quicksort is the most common sorting algorithm in use today. In light of its technological impact, it's good to know how it works.
Fundamentally, Quicksort is akin to merge sort, in that it seeks to partition the set into two pieces and then recursively sort each piece. Mergesort simply whacks the set into two equal-sized pieces, which has the side effect of requiring a non-trivial merging process to re-join the sorted sub-pieces.
Rather than split the set (array) into two arbitrary and equal-sized pieces, Quicksort divides the set into subsets where one subset contains values that are all smaller than a given "pivot value" while the other subset are all values that are greater than the pivot. Some implementations put the pivot in the set of smaller numbers and some put it in the set of larger numbers and still others keep it completely separate.
Joining the sorted subsets is trivial because we already know that one set is completely smaller than the other set.
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!
| 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;
}
}
|
Download the support code for this lab|^LabQuicksort.zip|\. Look at the base quicksort implementation (QuickSortBasic class), at the tests offered and at the Main program.
...