Partition Sort
PG: Scrap. Scrap all. Two reasons. (1) While sorting algorithms is an important and traditional CS topic, it's not obvious to me why they have any important role in an attract-them-in course. These are TiF for interested kids. (2) If our reason for this unit is to teach recursion, sorting is a distraction, and harder than we need to be. If anything at all, it's a culmination, not a start. I'd be happier showing kids how to march down a list and act on it. With HoFs or recursion. Power and utility. That's currently in Lab 4. Maybe earlier even than this unit?
BH: Definitely replace with mergesort. Partition sort isn't guaranteed O(n log n); its analysis was awarded a PhD at Stanford. Mergesort is straightforward.
MF: I said keep, but I find these pages to be almost to much, and I want to review them. Also, I want to think about whether it would make sense to revisit timing and efficiency here.
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.
Obsolete
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?