Quicksort

IB Syllabus: B2.4.4 (HL) – Recursive algorithms including quicksort; complexity and memory usage.

This page is HL only.

Table of Contents

  1. Key Concepts
    1. What is Quicksort?
    2. The Algorithm
    3. Choosing a Pivot
  2. Partition Step by Step
    1. Tracing Partition
  3. Complete Quicksort Implementation
    1. Tracing the Full Sort
  4. Complexity Analysis
    1. Time Complexity
    2. Space Complexity
    3. Comparison with Other Sorts
  5. Quick Check
  6. Trace Exercise
  7. Code Completion
  8. Spot the Error
  9. Practice Exercises
    1. Core
    2. Extension
    3. Challenge
  10. Connections

Key Concepts

What is Quicksort?

Quicksort is a divide-and-conquer sorting algorithm that works by:

  1. Choosing a pivot element
  2. Partitioning the array so that elements smaller than the pivot go to the left and elements larger go to the right
  3. Recursively sorting the left and right sub-arrays

After partitioning, the pivot is in its final sorted position. Repeat for each sub-array until every element is in place.

The Algorithm 

quicksort(arr, low, high):
    if low < high:
        pivotIndex = partition(arr, low, high)
        quicksort(arr, low, pivotIndex - 1)    // sort left side
        quicksort(arr, pivotIndex + 1, high)   // sort right side

The key is the partition step. After partitioning:

  • All elements to the left of the pivot are smaller (or equal)
  • All elements to the right are larger
  • The pivot is in its correct final position

Choosing a Pivot

Common strategies:

  • Last element (simplest, used in this page)
  • First element
  • Middle element
  • Median of three (first, middle, last – best in practice)

The choice of pivot affects performance. A bad pivot (smallest or largest element) leads to worst-case behaviour.

Partition Step by Step

The partition algorithm uses a pointer i that tracks where the “boundary” between small and large elements is.

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // choose last element as pivot
    int i = low - 1;        // i tracks the boundary

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // place pivot in its correct position
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;  // return pivot's final index
}

Tracing Partition

Partition the array [8, 3, 1, 7, 0, 10, 2] with pivot = 2 (last element).

j arr[j] arr[j] <= 2? Action Array State
– – – Start: i = -1, pivot = 2 [8, 3, 1, 7, 0, 10, 2]
0 8 No Skip [8, 3, 1, 7, 0, 10, 2]
1 3 No Skip [8, 3, 1, 7, 0, 10, 2]
2 1 Yes i=0, swap arr[0] and arr[2] [1, 3, 8, 7, 0, 10, 2]
3 7 No Skip [1, 3, 8, 7, 0, 10, 2]
4 0 Yes i=1, swap arr[1] and arr[4] [1, 0, 8, 7, 3, 10, 2]
5 10 No Skip [1, 0, 8, 7, 3, 10, 2]
– – – Place pivot: swap arr[2] and arr[6] [1, 0, 2, 7, 3, 10, 8]

Result: Pivot (2) is at index 2. Everything to the left [1, 0] is smaller. Everything to the right [7, 3, 10, 8] is larger. The pivot is in its final sorted position.

Complete Quicksort Implementation 

public static void quicksort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quicksort(arr, low, pivotIndex - 1);    // sort left
        quicksort(arr, pivotIndex + 1, high);   // sort right
    }
}

// Call from main:
int[] data = {8, 3, 1, 7, 0, 10, 2};
quicksort(data, 0, data.length - 1);
// Result: [0, 1, 2, 3, 7, 8, 10]

Tracing the Full Sort 

quicksort([8,3,1,7,0,10,2], 0, 6)
  partition → pivot=2 at index 2 → [1,0,2,7,3,10,8]
  quicksort([1,0], 0, 1)
    partition → pivot=0 at index 0 → [0,1]
    quicksort([], 0, -1) → base case
    quicksort([1], 1, 1) → base case
  quicksort([7,3,10,8], 3, 6)
    partition → pivot=8 at index 5 → [7,3,8,10]
    quicksort([7,3], 3, 4)
      partition → pivot=3 at index 3 → [3,7]
    quicksort([10], 6, 6) → base case
Result: [0, 1, 2, 3, 7, 8, 10]

Complexity Analysis

Time Complexity

Case Complexity When
Best O(n log n) Pivot always splits the array roughly in half
Average O(n log n) Random data, pivot gives reasonable splits
Worst O(n^2) Pivot is always the smallest or largest element (already sorted data with last-element pivot)

Why O(n log n) average? Each partition scans n elements (O(n)). If the pivot splits the array in half, there are log n levels of recursion. Total: O(n) * O(log n) = O(n log n).

Why O(n^2) worst case? If the pivot is always the smallest element, one side has n-1 elements and the other has 0. This creates n levels of recursion, each scanning n elements: O(n) * O(n) = O(n^2).

Space Complexity

O(log n) on average for the call stack (log n levels of recursion). O(n) in the worst case.

Comparison with Other Sorts

Algorithm Best Average Worst In-place?
Bubble Sort O(n) O(n^2) O(n^2) Yes
Selection Sort O(n^2) O(n^2) O(n^2) Yes
Quicksort O(n log n) O(n log n) O(n^2) Yes

Quicksort is much faster than bubble and selection sort on average. Its O(n^2) worst case can be avoided by choosing a good pivot (e.g., median of three).

Quicksort is the fastest general-purpose comparison sort in practice, despite its O(n^2) worst case.

Quick Check

Q1. What type of algorithm is quicksort?

Q2. What is true about the pivot after the partition step?

Q3. When does quicksort perform at O(n^2)?

Q4. What is quicksort's average time complexity?

Q5. What is the base case for quicksort's recursion?

Trace Exercise

Trace the first partition of [5, 1, 9, 3, 7] using the last element (7) as the pivot.

Trace: Track i and the array state after each comparison. Pivot = 7 (last element), i starts at -1.

jarr[j]arr[j] <= 7?i afterArray after swap
0 5 [5, 1, 9, 3, 7] (swap 5 with itself)
1 1 [5, 1, 9, 3, 7] (swap 1 with itself)
2 9 [5, 1, 9, 3, 7] (no swap)
3 3

Final: place pivot at i+1 = . Array becomes:

Code Completion

Complete the quicksort method.

Fill in the blanks: Complete the recursive quicksort.

public static void quicksort(int[] arr, int low, int high) {
    if (low < ) {
        int pivotIndex = (arr, low, high);
        quicksort(arr, low, pivotIndex - );
        quicksort(arr, pivotIndex + 1, );
    }
}

Spot the Error

This partition always puts the pivot at the wrong position.

Bug Hunt: The pivot ends up in the wrong position after partitioning.

1int pivot = arr[high]; 2int i = low - 1; 3for (int j = low; j < high; j++) { 4 if (arr[j] <= pivot) { i++; swap(arr, i, j); } 5swap(arr, i, high); // place pivot 6return i;

Pick the correct fix for line 5:

Practice Exercises

Core

  1. Trace a partition – Partition the array [6, 2, 8, 4, 1] using the last element (1) as the pivot. Show the array state after each comparison and the final position of the pivot.

  2. Complexity questions – Answer each:
    • (a) What is quicksort’s average time complexity?
    • (b) What causes the O(n^2) worst case?
    • (c) How can the worst case be avoided?
  3. Compare – Create a table comparing quicksort, bubble sort, and selection sort across: best case, average case, worst case, and whether the algorithm is in-place.

Extension

  1. Full trace – Trace the complete quicksort of [4, 7, 2, 1, 5, 3]. Show every partition step and recursive call until the array is fully sorted.

  2. Quicksort on objects – Adapt the quicksort implementation to sort an array of Student objects by grade in ascending order. Use getter methods for comparison and swap object references.

Challenge

  1. Worst-case demonstration – Show step by step why quicksort degrades to O(n^2) on the already-sorted array [1, 2, 3, 4, 5] when using the last element as the pivot. Count the total number of comparisons and compare with the average case.

Connections

© EduCS.me — A resource hub for IB Computer Science

This site uses Just the Docs, a documentation theme for Jekyll.