Quicksort: partitioning, best, worst and average cases

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Worst-case comparisons of merge sort on 8 elements? from Lesson 3.2.1
• T(n) = T(n/10) + T(9n/10) + n? from Lesson 1.2.4
• Which sorts are in-place? from Lesson 3.1.2

1 · The Hook

🎣

Quicksort is the sort most libraries actually use: in-place and usually the fastest. It picks a pivot, moves smaller elements left and larger ones right, and recurses. On unlucky inputs it degrades to n², and GATE asks exactly when that happens.

2 · Predict First

🤔

Partition A = [5, 2, 9, 1, 7, 3] around the last element, 3 (Lomuto scheme: scan left to right, moving every element ≤ pivot to the growing left part, then put the pivot after them). Where does 3 end up?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Elements ≤ 3 are 2 and 1. After partitioning: [2, 1, 3, 5, 7, 9]: the pivot 3 lands at index 2, its final sorted position.

Lomuto partition (pivot = last element)

int partition(A, lo, hi) {
    p = A[hi]; i = lo - 1;
    for (j = lo; j < hi; j++)
        if (A[j] <= p) { i++; swap(A[i], A[j]); }
    swap(A[i + 1], A[hi]);
    return i + 1;               // pivot's final index
}

• Exactly hi − lo comparisons (n − 1 for n elements).
• Afterwards: left part ≤ pivot, pivot in its final position, right part > pivot.

Quicksort

void qsort(A, lo, hi) {
    if (lo < hi) { q = partition(A, lo, hi); qsort(A, lo, q - 1); qsort(A, q + 1, hi); }
}

Worst-case inputs with a first- or last-element pivot: already sorted or reverse-sorted arrays; with Lomuto, also an array of all equal elements.

Fixes

• Random pivot or median-of-three: makes the worst case unlikely (still Θ(n²) worst).
• True median as pivot (found in Θ(n), Lesson 3.3.3): worst case Θ(n log n), but large constants.

Space and stability

• In-place partitioning; recursion stack: worst depth n, best log n (O(log n) if you recurse on the smaller side first and loop on the larger).
• Not stable.

Hoare partition (brief)

Two indices move toward each other from both ends and swap pairs on the wrong side; fewer swaps than Lomuto, but the pivot need not end in its final place.

4 · Visual

Lomuto on [5, 2, 9, 1, 7, 3], pivot 3          i marks the end of the "<= 3" part

j=0: 5 > 3                       [5 2 9 1 7 | 3]
j=1: 2 <= 3 -> i=0, swap A0,A1   [2 5 9 1 7 | 3]
j=2: 9 > 3
j=3: 1 <= 3 -> i=1, swap A1,A3   [2 1 9 5 7 | 3]
j=4: 7 > 3
end: swap A2 with pivot          [2 1 3 5 7 9]   pivot index 2, 5 comparisons

5 · Worked Examples

Example 1 Easy

How many comparisons does quicksort (last-element pivot) make on the sorted array [1, 2, 3, 4, 5, 6]?

Solution

5 + 4 + 3 + 2 + 1 = 15 = n(n − 1)/2.

Example 2 Medium

Lomuto partition of [7, 2, 8, 1, 6, 3, 5, 4] with pivot 4. Resulting array and pivot index?

Solution

Elements ≤ 4: 2, 1, 3. Result [2, 1, 3, 4, 6, 8, 5, 7], pivot at index 3.

Example 3 GATE

Quicksort picks the n/4-th smallest element as pivot every time, found in Θ(n). Worst-case time?

Solution

T(n) = T(n/4) + T(3n/4) + Θ(n) → Θ(n log n).

6 · GATE Traps

⚠️

• First/last-element pivot: sorted input is the worst case.
• Any constant-fraction split still gives Θ(n log n).
• Lomuto on all-equal keys is Θ(n²).
• Quicksort is in-place but not stable; its recursion can use Θ(n) stack in the worst case.

7 · Memory Hook

🧠

"Partition puts the pivot home; bad pivots make n²."

8 · Connect the Dots

Merge sort works after splitting; quicksort works before. Next: heapsort, which gets Θ(n log n) worst case and in-place, using the binary heap from Lesson 0.2.2.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markPartition result

Lomuto partition (pivot = last) of [5, 2, 9, 1, 7, 3]. Result?

• (A) [3, 2, 1, 5, 7, 9]
• (B) [2, 1, 3, 9, 7, 5]
• (C) [1, 2, 3, 5, 7, 9]
• (D) [2, 1, 3, 5, 7, 9]

Q2NAT1 markPartition comparisons

Lomuto partition of a 20-element subarray makes how many comparisons?

Numerical answer: ________

Q3NAT2 marksWorst case

Quicksort with last-element pivot on a sorted array of 10 elements. Total comparisons?

Numerical answer: ________

Q4MCQ1 markConstant split

If every partition splits the array 1 : 99, quicksort runs in:

• (A) Θ(n)
• (B) Θ(n log n)
• (C) Θ(n²)
• (D) Θ(n^1.5)

Q5NAT2 marksTotal comparisons

Quicksort (Lomuto, last-element pivot) on [5, 2, 9, 1, 7, 3]. Total comparisons over all partitions?

Numerical answer: ________

10 · Rule Card

• Lomuto: pivot = last; n − 1 comparisons; pivot ends in its final place.
• Best/average Θ(n log n); worst Θ(n²) (sorted or reverse with end pivot; all-equal with Lomuto).
• Constant-fraction splits → Θ(n log n). Median pivot (Θ(n)) → worst Θ(n log n).
• In-place, not stable; stack O(log n) best, O(n) worst.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

pivotLomuto partitionHoare partition (brief)quicksortbest, average, worst case of quicksortrandom pivotmedian-of-threerecursion stack of quicksort

12 · Answer Vault