CSS Prepare

optional · CSS study notes

Quick Sort

Mechanism (Divide and Conquer, In-Place)

  1. Choose a pivot element (first, last, random, or median-of-three)
  2. Partition: rearrange array so elements < pivot go left, elements > pivot go right
  3. Recurse on left and right partitions

Pseudocode

QUICK_SORT(arr, low, high):
  IF low < high:
    p = PARTITION(arr, low, high)
    QUICK_SORT(arr, low, p-1)
    QUICK_SORT(arr, p+1, high)

Complexity

  • Best/Average: O(n log n)
  • Worst: O(n²) — occurs when pivot selection is consistently poor (e.g., already-sorted array with first-element pivot) causing maximally unbalanced partitions
  • Space: O(log n) average (recursion stack, in-place sort — no extra array needed)
  • Not stable by default

Why It's Usually Preferred Over Merge Sort in Practice

  • In-place (O(log n) space vs Merge Sort's O(n)) and has smaller constant factors — faster in practice despite same average complexity, provided pivot selection avoids worst case (randomized/median-of-three pivot mitigates this)

Exam Angle / MCQ Trap

High-frequency question: "Explain why Quick Sort's worst case is O(n²) and how to avoid it." Answer: poor/deterministic pivot choice on already-sorted or reverse-sorted data — mitigated via randomized pivot or median-of-three selection.

📌 Sample & Repeated FPSC Questions (2016–2026)

2025, Paper I, Q6(c) (8 marks) — Sort the parcel weights [30, 45, 10, 20, 75, 15, 85, 40, 5, 65] in ascending order using Quick Sort. Clearly indicate the choice of pivot and reason for it, with a graphical representation of each step.

Pivot choice: last element of each (sub)array (Lomuto partition scheme) — simple, in-place (no extra memory), and gives good average-case O(n log n) performance; it's the classic textbook scheme (production libraries usually add median-of-three on top to dodge the worst case).

Array (idx 0-9): [30, 45, 10, 20, 75, 15, 85, 40, 5, 65]

QS(0,9)  pivot=65 → partition:
  [30, 45, 10, 20, 15, 40, 5 | 65 | 85, 75]        (65 fixed at idx 7)

QS(8,9)  pivot=75 (right part [85,75]) → [75 | 85]
  → [ ... , 65, 75, 85]                             (idx 7,8,9 fixed)

QS(0,6)  pivot=5 (left part [30,45,10,20,15,40,5]) → partition:
  [5 | 45, 10, 20, 15, 40, 30]                      (5 fixed at idx 0)

QS(1,6)  pivot=30 ([45,10,20,15,40,30]) → partition:
  [10, 20, 15 | 30 | 40, 45]                        (30 fixed at idx 4)

QS(1,3)  pivot=15 ([10,20,15]) → partition:
  [10 | 15 | 20]                                    (15 fixed; 10, 20 already single)

QS(5,6)  pivot=45 ([40,45]) → already ordered → [40 | 45]

Final sorted array: [5, 10, 15, 20, 30, 40, 45, 65, 75, 85]

Key reasoning points:

  • Each partition pass fixes exactly one pivot into its final sorted position and produces two smaller subarrays — the recursion in this page's pseudocode (QUICK_SORT(arr, low, p-1) / QUICK_SORT(arr, p+1, high)) is exactly what's being traced above.
  • This particular input is close to random-order, so partitions stay reasonably balanced — contrast with the page's Exam Angle box: an already-sorted input with last-element pivot is the classic O(n²) trigger, because every partition would then be maximally unbalanced (n-1 vs 0).

2024, Paper I, Q6(a) (8 marks) — For various dataset types, which sorting algorithms work well and which don't? (see the "Searching & Sorting (2017)" page for the full 10-part table)

Exam angle for Quick Sort specifically: Quick Sort is the go-to answer for general-purpose in-memory sorting of medium-to-large datasets (1,000 to ~1 million elements) of ints, floats, or names — provided pivot selection (randomized or median-of-three) avoids already-sorted/adversarial worst-case input. It is not the best choice when a guaranteed worst case is required (prefer Merge/Heap Sort instead) or when values have a small known range (Counting Sort) or are uniformly distributed (Bucket Sort) — both beat Quick Sort's O(n log n) with near-O(n) performance in those special cases.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2025 · Paper-I · Q6(c) · 8 marks

Q. Use quick sort to sort the parcel weights [30, 45, 10, 20, 75, 15, 85, 40, 5, 65] in ascending order. Clearly indicate the pivot and the reason, and show each step.

Ans.

  • Pivot choice: the last element of each sub-array (simple to implement). A median-of-three pivot is better on sorted input, because the last-element pivot can give O(n²).
  • Step 1: pivot = 65. Elements less than 65 move to the left, the larger ones to the right.
[30 45 10 20 15 40 5]  65  [85 75]
  • Step 2 (left part): pivot = 5. Nothing is smaller, so it goes first.
5  [45 10 20 15 40 30]
  • Step 3: pivot = 30. Smaller: 10, 20, 15.
[10 20 15]  30  [40 45]
  • Step 4: pivot = 15 in [10 20 15] → [10] 15 [20]. [40 45] with pivot 45 → [40] 45.
  • Step 5 (right part of step 1): [85 75] with pivot 75 → 75 85.
  • Sorted result: 5 10 15 20 30 40 45 65 75 85.
  • Complexity: average O(n log n), worst case O(n²), extra space O(log n).