Quicksort Partition

Given an array of integers arr and a number pivot, modify arr in place using only O(1) extra space so that:

  1. Every element smaller than the pivot appears before every element greater than or equal to the pivot.
  2. Every element larger than the pivot appears after every element smaller than or equal to the pivot.

The relative order of the elements smaller than or greater than the pivot does not matter.

Example 1:

  • Input: arr = [3, 7, 1, 3, 3, 3, 2], pivot = 4
  • Output: [3, 2, 1, 3, 3, 3, 7]
  • Explanation: Other orders such as [3, 2, 1, 3, 3, 3, 7] are valid.
1def partition(arr: List[int], pivot: int) -> None:
2    l, r = 0, len(arr) - 1
3    
4    while l <= r:
5        while l <= r and arr[l] < pivot:
6            l += 1
7        while l <= r and arr[r] >= pivot:
8            r -= 1
9            
10        if l < r:
11            arr[l], arr[r] = arr[r], arr[l]
12            l += 1
13            r -= 1
Previous
Parity Sorting
Next
Dutch Flag Problem
l
3
0
7
1
1
2
3
3
3
4
3
5
r
2
6
Step 1 / 6
Step 1:
Initialize l=0, r=6. Pivot is 4.
Pointers: l=0, r=6
Focus: select @ [0, 6]