Page 3: Partition Sort

Unit 8, Lab 6, Page 3

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.

  • 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 list{Emma, Olivia, Sophia, Isabella, Ava, Mia, Emily, Abigail} , 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.

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

  1. How is a partition sort an example of recursion? What is the base case?

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.

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

If There Is Time…

  1. 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:
    set(biglist) to (Empty list); repeat(500){add(pick random(1) to (2000) to (biglist)}; reset timer; say(sort(biglist)); set(time) to (timer)

  1. Which algorithm was fastest? Why might this type of algorithm run faster?