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