Partition Sort
Another commonly used sort is called a partition sort. Here's how it works:
- Step 1. In an unsorted list, select the first item in the list (which probably won't be the item that should appear first after sorting). This item is called a pivot.
BH: About step 2 and its yellow box: This handwaves away the deep issue, which is that sometimes the sort key is smaller than the sort record, so two records may sort alike but not be equal. I'm not sure if this has to be addressed but maybe it should be mentioned in the TG. BK: I didn't understand what this comment means, sorry.
An item is "with the pivot" only if it has the same value as the pivot.
Step 2. For each item in the list, decide if it comes before the pivot, with the pivot, or after the pivot.- Step 3. Partition the data into three categories: items before the pivot, with the pivot, after the pivot. The lists before and after the pivot are unsorted.
- Step 4. If there are items before the pivot, use a partition sort to put them in order. If there are items after the pivot, use a partition sort to put them in order.
- Step 5.The sorted list is made from appending the three result lists together.
Names aren't sorted while placing them before or after a pivot. For
, this is the status after the first split via pivoting: the
pivot is Emma, the list before the pivot is
{Ava, Abigail}, and the list after the pivot is
{Olivia, Sophia, Isabella, Mia, Emily}. The sorting process then continues on these two smaller unsorted lists.
- Explore the partition sort before writing any code. With your class, stand up and form a line. Then, follow the partition sort process to put everyone in sorted order, low to high, by the number of their home address.
- How is a partition sort an example of recursion? What is the base case?
We may want to make our own video to show this in action. The linked video is not quite right and has been killed off.
To write a partition sort block in Snap!, you'll need code for a base case, and code that follows the steps of the partition sort.
-
Examine this new project containing the append block (Variables menu).
- Describe what the
append block does.
You'll need to figure out how to place the items into the three categories, and how to create one final list to output.
Build the recursive reporter partition sort. Its output, for any list, should be the same as the output for selection sort.
Reveal an example.
For example, let's say yesterday you had a big sorted list, and today you add a few new items, so you need to re-sort the list. A general-purpose sorting algorithm won't take advantage of the almost-in-order character of its input. But insertion sort, an algorithm that's slow in general, handles this special case quickly.
Why are there different sorting algorithms? Some sorting algorithms take longer than others to run, but even an algorithm that's slow in general may be useful in special cases.
-
You could also use a long list of names here.
Make a 500-item list of random numbers, and then sort the list using the three sorting algorithms you built in this lab. Keep track of the timings:
- Which algorithm was fastest? Why might this type of algorithm run faster?