Learn
Quicksort: Python
Partitioning Party

We need to partition our list into two sub-lists of greater than or smaller than elements, and we’re going to do this “in-place” without creating new lists. Strap in, this is the most complex portion of the algorithm!

Because we’re doing this in-place, we’ll need two pointers. One pointer will keep track of the “lesser than” elements. We can think of it as the border where all values at a lower index are lower in value to the pivot. The other pointer will track our progress through the list.

Let’s explore how this will work in an example:

[5, 6, 2, 3, 1, 4] # we randomly select "3" and swap with the last element [5, 6, 2, 4, 1, 3] # We'll use () to mark our "lesser than" pointer # We'll use {} to mark our progress through the list [{(5)}, 6, 2, 4, 1, 3] # {5} is not less than 3, so the "lesser than" pointer doesn't move [(5), {6}, 2, 4, 1, 3] # {6} is not less than 3, so the "lesser than" pointer doesn't move [(5), 6, {2}, 4, 1, 3] # {2} is less than 3, so we SWAP the values... [(2), 6, {5}, 4, 1, 3] # Then we increment the "lesser than" pointer [2, (6), {5}, 4, 1, 3] [2, (6), 5, {4}, 1, 3] # {4} is not less than 3, so the "lesser than" pointer doesn't move [2, (6), 5, 4, {1}, 3] # {1} is less than 3, so we SWAP the values... [2, (1), 5, 4, {6}, 3] # Then we increment the "lesser than" pointer [2, 1, (5), 4, {6}, 3] # We've reached the end of the non-pivot values [2, 1, (5), 4, 6, {3}] # Swap the "lesser than" pointer with the pivot... [2, 1, (3), 4, 6, {5}]

Tada! We have successfully partitioned this list. Note that the “sub-lists” are not necessarily sorted, we’ll need to recursively run the algorithm on each sub-list, but the pivot has arrived at the correct location within the list.

Instructions

1.

Create the variable lesser_than_pointer and assign it to the start of the list.

2.

Create a for loop that iterates from start to end, and set the iterating variable to idx. This will track our progress through the list (or sub-list) we’re partitioning.

To start, write continue in the for loop.

3.

Within the loop, remove continue and replace it with a conditional.

We need to do something if the element at idx is less than pivot_element.

If so:

  1. Use parallel assignment to swap the values at lesser_than_pointer and idx.
  2. Increment the lesser_than_pointer
4.

Once the loop concludes, use parallel assignment to swap the pivot element with the value located at lesser_than_pointer.

Here’s an example:

colors = ["blue", "red", "green"] colors[0], colors[1] = colors[1], colors[0] # ["red", "blue", "green"]
Folder Icon

Sign up to start coding

Already have an account?