Quick Sort

medium

Implement quicksort with partition — the most important sort for interviews

Quick Sort (Partition)

Key Insight

Partition places pivot in correct position — elements left are smaller, right are larger

Step 1Choose Pivot
Pivot: 70
i
j
10
0
80
1
30
2
90
3
40
4
50
5
70
6

Pick last element (70) as pivot. Goal: put everything < 70 left, > 70 right.

1 / 7

Learn the Pattern

SortingUse sorting as a preprocessing step to simplify problems, or apply partition logic for in-place rearrangement. Many interview problems become trivial once the array is sorted.
Practice the Code

Step-by-Step Walkthrough: Quick Sort (Partition)

Partition places pivot in correct position — elements left are smaller, right are larger

  1. Choose Pivot

    Pick last element (70) as pivot. Goal: put everything < 70 left, > 70 right.

  2. Scan: 10 < 70

    10 < pivot. Swap arr[i] with arr[j], advance i. (10 stays in place)

  3. Scan: 80 ≥ 70

    80 ≥ pivot. Skip (j advances but i stays).

  4. Scan: 30 < 70

    30 < pivot. Swap 30 with 80 (swap arr[i] and arr[j]).

  5. Continue Scanning

    90 ≥ 70 skip. 40 < 70 swap with 80. 50 < 70 swap with 90.

  6. Place Pivot

    Swap pivot (70) with arr[i] (80). Pivot is now at index 4 — its CORRECT position!

  7. Recurse Both Sides

    Recursively quicksort [10, 30, 40, 50] and [90, 80]. Each partition places one more element.