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!
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.
Also download the lecture notes on this subject.
Exercises:
- Starting from QuickSortBasic, build the task-decomposed version of QuickSort to in slide 17 of the lecture.
- Starting from QuickSort with Tasks, build the parallel version of QuickSort to in slide 21 of the lecture.
- Starting from the parallel version of quicksort, build a more efficient parallel version, where the parallel tasks are created only at the topmost level, and all subsequent recursive calls are performed sequentially.
- Improve the above version by selecting the median element of the array as pivot.
Note: To analyze the performance of the parallel algorithm, use an input ArrayList that gets sorted in a few seconds on your machine.