Partitioning

To partition an array is to take a random value from the array—which is then called the pivot—and make sure that every number that is less than the pivot ends up to the left of the pivot and that every number greater than the pivot ends up to the right of the pivot. We accomplish partitioning through a simple algorithm that will be described in the following example.

Let’s say we have the following array:

For consistency’s sake, we’ll always select the rightmost value to be our pivot (although we can technically choose other values). In this case, the number 3 is our pivot. We indicate this by circling it:

We then assign pointers—one to the leftmost value of the array, and one to the rightmost value of the array, excluding the pivot itself:

We’re now ready to begin the actual partition, which follows these steps. Don’t worry—the steps will become clearer shortly, when we walk through our example.

1. The left pointer continuously moves one cell to the right until it reaches a value that is greater than or equal to the pivot and then stops.

2. Then the right pointer continuously moves one cell to the left until it reaches a value that is less than or equal to the pivot and then stops. The right pointer will also stop if it reaches the beginning of the array.

3. Once the right pointer has stopped, we reach a crossroads. If the left pointer has reached (or gone beyond) the right pointer, we move on to Step 4. Otherwise, we swap the values that the left and right pointers are pointing to, and then we go back to repeat Steps 1, 2, and 3 again.

4. Finally, we swap the pivot with the value that the left pointer is currently pointing to.

When we’re done with a partition, we are now assured that all values to the left of the pivot are less than the pivot, and all values to the right of the pivot are greater than it. And that means the pivot itself is now in its correct place within the array, although the other values are not yet necessarily completely sorted.

Let’s apply this to our example:

Step 1: Compare the left pointer (now pointing to 0) to our pivot (the value 3):

Since 0 is less than the pivot, the left pointer moves on in the next step.

Step 2: The left pointer moves on:

We compare the left pointer (the 5) to our pivot. Is the 5 lower than the pivot? It’s not, so the left pointer stops, and we activate the right pointer in our next step.

Step 3: Compare the right pointer (6) to our pivot. Is the value greater than the pivot? It is, so our pointer will move on in the next step.

Step 4: The right pointer moves on:

We compare the right pointer (1) to our pivot. Is the value greater than the pivot? It’s not, so our right pointer stops.

Step 5: Since both pointers have stopped, we swap the values of the two pointers:

We then activate our left pointer again in the next step.

Step 6: The left pointer moves on:

We compare the left pointer (2) to our pivot. Is the value less than the pivot? It is, so the left pointer moves on.

Step 7: The left pointer moves on to the next cell. Note that at this point, both the left and right pointers are pointing to the same value:

We compare the left pointer to our pivot. Because our left pointer is pointing to a value that is greater than our pivot, it stops. At this point, since our left pointer has reached our right pointer, we’re done with moving pointers.

Step 8: For our final step of the partition, we swap the value that the left pointer is pointing to with the pivot:

Although our array isn’t completely sorted, we’ve successfully completed a partition; that is, since our pivot was the number 3, all numbers that are less than 3 are to its left, while all numbers greater than 3 are to its right. This also means, by definition, that the 3 is now in its correct place within the array.

Code Implementation: Partitioning

Following is an implementation of a SortableArray class in Python that includes a partition method that partitions the array as we’ve described:

Let’s break this code down a bit.

The partition method accepts the starting points of the left and right pointers as parameters:

When this method is first called on an array, these pointers will point to the left and right ends of the array, respectively. However, we’ll see that Quicksort will call this method on subsections of the array as well. Because of this, we can’t always assume the left and right pointers are always the two extremities of the array, so they need to become method arguments. This point will be clearer when I explain the complete Quicksort algorithm.

Next, we select our pivot, which is always the rightmost element in the range we’re dealing with:

Once our pivot has been identified, we move the right_pointer to the item immediately left of the pivot:

We then begin a loop (while True) that will seem to run indefinitely. However, later within the loop is a break statement that will terminate the loop as soon as the left_pointer and right_pointer cross paths. Within this loop, we use another loop to keep moving the left_pointer to the right until it reaches an item that is greater than or equal to the pivot:

Similarly, we move the right_pointer to the left until it hits an item that is less than or equal to the pivot:

Once the left_pointer and right_pointer have stopped moving, we check whether the two pointers have met:

If they have, we exit the loop and get ready to swap out the pivot, which we’ll get to momentarily. However, if the two pointers have stopped but not yet met each other, we swap the values at the two pointers:

We then move the left_pointer to get ready for the next round of left- and right-pointer movements:

Finally, once the two pointers have met, we swap the pivot with the value at the left_pointer:

The method concludes by returning the left_pointer, as this will be needed by the Quicksort algorithm (which I’ll explain shortly).