Writing the Pivot Function in Quicksort

Back to: Python Data Structure and Algorithims

Writing the Pivot Function in Quicksort

Now that we understand what the pivot function does conceptually, let’s write the actual code for it.

This function is responsible for:

Rearranging elements around a pivot.
Returning the pivot index for recursive quicksort calls.

Step 1: Create a Swap Helper Function

Since we’ll be swapping items in multiple places, it’s cleaner to create a small swap function first:

This lets us reuse the code whenever we need to exchange two elements in a list.

Step 2: Define the Pivot Function

The pivot function will take three parameters:

lst → the list we want to sort.
pivot_index → the starting index of the pivot (usually 0).
end_index → the last index in the current portion of the list.

def pivot(lst, pivot_index, end_index):

swap_index = pivot_index # This will track where to swap smaller elements

for i in range(pivot_index + 1, end_index + 1):

if lst[i] < lst[pivot_index]:

swap_index += 1

swap(lst, swap_index, i) # Swap the current element with swap_index

# Place the pivot in its correct position

swap(lst, pivot_index, swap_index)

return swap_index # Return the index where pivot is now loc

Step 3: How It Works with an Example

Let’s take this list:

We run:

Step-by-step execution:

Initial variables:
- pivot_value = 4
- pivot_index = 0
- swap_index = 0
Loop through list and compare each element with the pivot:
- 6 > 4 → no swap
- 1 < 4 → move swap_index to 1, swap 6 and 1 → [4, 1, 6, 7, 3, 2, 5]
- 7 > 4 → no swap
- 3 < 4 → move swap_index to 2, swap 6 and 3 → [4, 1, 3, 7, 6, 2, 5]
- 2 < 4 → move swap_index to 3, swap 7 and 2 → [4, 1, 3, 2, 6, 7, 5]
- 5 > 4 → no swap
Final pivot swap: Swap pivot 4 with element at swap_index = 3:

Return pivot index: 3

Step 4: Outcome

After running the pivot function:

The pivot 4 is in its correct sorted position.
All elements less than 4 are on the left.
All elements greater than 4 are on the right.

This prepares the list for recursive quicksort calls on the left and right sublists.

Next, we can use this pivot function to implement the full quicksort algorithm, recursively sorting each side until the entire list is sorted.