Back to: Python Data Structure and Algorithims
Understanding the Pivot Function in Quicksort
In this section, we’re going to walk through how the pivot function works — a helper function that plays a crucial role in the quicksort algorithm.
Just like we used the merge() function as a helper in merge sort, the pivot() function helps quicksort organize elements efficiently.
What Does the Pivot Function Do?
The pivot function takes a list, picks one element as the pivot, and rearranges the list so that:
-
All numbers smaller than the pivot go to the left, and
-
All numbers greater than the pivot go to the right.
After this operation, the pivot is exactly where it would be if the list were fully sorted.
This helps quicksort break the list into smaller sublists that can be recursively sorted.
Example: Step-by-Step Explanation
Let’s take the following list as an example:
We’ll use the first element (4) as our pivot.
Step 1: Initialize pointers
-
pivot_value = 4 -
pivot_index = 0 -
swap_index = 0
We’ll loop through the list starting from index 1.
Step 2: Compare each element to the pivot
| i | Current Element | Comparison | Action | swap_index | List after swap |
|---|---|---|---|---|---|
| 1 | 6 | 6 > 4 | No swap | 0 | [4, 6, 1, 7, 3, 2, 5] |
| 2 | 1 | 1 < 4 | Move swap_index to 1, swap 6 and 1 | 1 | [4, 1, 6, 7, 3, 2, 5] |
| 3 | 7 | 7 > 4 | No swap | 1 | [4, 1, 6, 7, 3, 2, 5] |
| 4 | 3 | 3 < 4 | Move swap_index to 2, swap 6 and 3 | 2 | [4, 1, 3, 7, 6, 2, 5] |
| 5 | 2 | 2 < 4 | Move swap_index to 3, swap 7 and 2 | 3 | [4, 1, 3, 2, 6, 7, 5] |
| 6 | 5 | 5 > 4 | No swap | 3 | [4, 1, 3, 2, 6, 7, 5] |
Step 3: Final swap
After the loop ends, swap the pivot element (4) with the element at swap_index (index 3).
Now, the pivot (4) is in the correct position — all smaller elements are on the left, and larger ones are on the right.
Step 4: Return the Pivot Index
The pivot function returns the index 3, which is the correct position of the pivot element 4.
This index is crucial for the next steps in quicksort:
-
Quicksort will now be applied to the left side:
[2, 1, 3] -
And the right side:
[6, 7, 5]
Summary
The pivot function:
-
Selects a pivot (first element).
-
Rearranges elements so that smaller ones are on the left and larger ones are on the right.
-
Swaps the pivot into its correct position.
-
Returns the pivot index for recursive sorting.
After the pivot step, the list [4, 6, 1, 7, 3, 2, 5] becomes [2, 1, 3, 4, 6, 7, 5],
and quicksort continues sorting the left and right halves recursively.