QuickSort and QuickSelect

Introduction

QuickSort is one of the most widely used sorting algorithms in practice — it's the default behind many standard library sort functions. QuickSelect is its lesser-known sibling that solves a very specific and common problem: finding the k-th smallest (or largest) element in an unsorted collection without sorting the entire thing. Both algorithms share the same core idea — partitioning — and understanding one gives you the key to the other.

Core Concepts

The Partitioning Idea

Imagine you're organizing a bookshelf. You pick one book at random (the pivot) and then move every book that comes alphabetically before it to the left, and every book that comes after it to the right. After one pass, you don't have a sorted shelf, but you know exactly where that one book belongs. That's partitioning.

Partitioning is the engine that powers both QuickSort and QuickSelect. After one partition step:

• The pivot element is in its final sorted position
• Everything to the left is smaller than or equal to the pivot
• Everything to the right is greater than or equal to the pivot

QuickSort — The Full Sort

QuickSort says: "After partitioning, recursively sort the left side and the right side." That's the entire algorithm. Its elegance is in its simplicity.

Time Complexity:

• Average case: O(n log n) — when pivots roughly split arrays in half
• Worst case: O(n²) — when pivots consistently land at the extremes (already sorted arrays with bad pivot choice)
• Space: O(log n) average for the recursion stack (in-place variant)

QuickSelect — Finding the K-th Element

QuickSelect says: "After partitioning, I only care about one side — the side where my target index lives." Instead of recursing on both halves, it only recurses on the half that contains the k-th element. This gives it an average time complexity of O(n) — linear time!

Think of it like a binary search, but instead of searching a sorted array, you're progressively narrowing down an unsorted array by partitioning.

Time Complexity:

• Average case: O(n) — each partition roughly halves the search space: n + n/2 + n/4 + ... ≈ 2n
• Worst case: O(n²) — same pathological pivot problem as QuickSort
• Space: O(1) if implemented iteratively, O(log n) if recursive

Partition Schemes

There are two classic partition schemes. Understanding both is important because interviewers may ask about either.

Lomuto Partition Scheme

The Lomuto scheme is simpler to understand and implement. It uses the last element as the pivot and maintains a boundary index i that tracks where the "small elements" section ends.

Hoare Partition Scheme

The Hoare scheme uses two pointers moving toward each other from opposite ends. It's more efficient in practice (fewer swaps on average) but slightly trickier to implement correctly.

Implementation — QuickSort

QuickSort with Lomuto Partition

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = lomutoPartition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function lomutoPartition(arr, low, high) {
  const pivot = arr[high]; // last element as pivot
  let i = low - 1; // boundary of "small" section

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // swap
    }
  }

  // Place pivot in its correct position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Usage
const data = [10, 7, 8, 9, 1, 5];
console.log(quickSort([...data])); // [1, 5, 7, 8, 9, 10]

// Edge cases
console.log(quickSort([]));        // []
console.log(quickSort([1]));       // [1]
console.log(quickSort([3, 3, 3])); // [3, 3, 3]
console.log(quickSort([5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5] (worst-case input for Lomuto)

QuickSort with Hoare Partition

function quickSortHoare(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = hoarePartition(arr, low, high);
    quickSortHoare(arr, low, pivotIndex);       // Note: includes pivotIndex
    quickSortHoare(arr, pivotIndex + 1, high);
  }
  return arr;
}

function hoarePartition(arr, low, high) {
  const pivot = arr[Math.floor((low + high) / 2)]; // middle element as pivot
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

// Usage
const data2 = [10, 7, 8, 9, 1, 5];
console.log(quickSortHoare([...data2])); // [1, 5, 7, 8, 9, 10]

Tracing Through a QuickSort Example

Let's trace quickSort([3, 6, 1, 8, 2, 5]) step by step:

Implementation — QuickSelect

The K-th Smallest Element Problem

Given an unsorted array, find the k-th smallest element. For example, in [3, 1, 4, 1, 5, 9], the 3rd smallest element is 3 (sorted: [1, 1, 3, 4, 5, 9]).

You could sort the array first (O(n log n)), but QuickSelect does it in O(n) on average.

function quickSelect(arr, k, low = 0, high = arr.length - 1) {
  // k is 1-indexed: 1st smallest, 2nd smallest, etc.
  // Convert to 0-indexed target position
  const targetIndex = k - 1;

  if (low === high) return arr[low];

  const pivotIndex = lomutoPartition(arr, low, high);

  if (pivotIndex === targetIndex) {
    return arr[pivotIndex]; // Found it!
  } else if (pivotIndex > targetIndex) {
    return quickSelect(arr, k, low, pivotIndex - 1); // Search left
  } else {
    return quickSelect(arr, k, pivotIndex + 1, high); // Search right
  }
}

// Reusing Lomuto partition from above
function lomutoPartition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Usage
const data = [3, 1, 4, 1, 5, 9, 2, 6];
console.log(quickSelect([...data], 1)); // 1  (1st smallest)
console.log(quickSelect([...data], 3)); // 2  (3rd smallest)
console.log(quickSelect([...data], 5)); // 4  (5th smallest)

// Finding the median
const median = quickSelect([...data], Math.ceil(data.length / 2));
console.log('Median:', median); // 3

QuickSelect Decision Flow

Iterative QuickSelect

The recursive version can be converted to an iterative one easily, saving stack space:

function quickSelectIterative(arr, k) {
  const targetIndex = k - 1;
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const pivotIndex = lomutoPartition(arr, low, high);

    if (pivotIndex === targetIndex) {
      return arr[pivotIndex];
    } else if (pivotIndex > targetIndex) {
      high = pivotIndex - 1;
    } else {
      low = pivotIndex + 1;
    }
  }

  return arr[low];
}

// Finding k-th largest (common interview variant)
function kthLargest(arr, k) {
  // k-th largest = (n - k + 1)-th smallest
  return quickSelectIterative([...arr], arr.length - k + 1);
}

console.log(kthLargest([3, 2, 1, 5, 6, 4], 2)); // 5 (2nd largest)
console.log(kthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4 (4th largest)

Pivot Selection Strategies

Pivot choice is critical for performance. A bad pivot leads to O(n²); a good pivot leads to O(n log n) for sort or O(n) for select.

Randomized Pivot

The simplest way to avoid worst-case behavior:

function randomizedPartition(arr, low, high) {
  // Pick a random pivot and swap it to the end
  const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
  [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
  return lomutoPartition(arr, low, high);
}

function randomizedQuickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = randomizedPartition(arr, low, high);
    randomizedQuickSort(arr, low, pivotIndex - 1);
    randomizedQuickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

console.log(randomizedQuickSort([5, 4, 3, 2, 1])); // No longer worst-case!

Median of Three

function medianOfThreePartition(arr, low, high) {
  const mid = Math.floor((low + high) / 2);

  // Sort low, mid, high so median is at mid
  if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];

  // Move median to high-1 position and use as pivot
  [arr[mid], arr[high]] = [arr[high], arr[mid]];
  return lomutoPartition(arr, low, high);
}

Three-Way Partition (Dutch National Flag)

When the array has many duplicate elements, standard QuickSort can degrade because duplicates don't get eliminated from future recursive calls. The three-way partition handles this elegantly:

function quickSort3Way(arr, low = 0, high = arr.length - 1) {
  if (low >= high) return arr;

  let lt = low;      // arr[low..lt-1]  < pivot
  let gt = high;     // arr[gt+1..high] > pivot
  let i = low;       // arr[lt..i-1]   == pivot
  const pivot = arr[low];

  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--;
      // Don't increment i — the swapped element needs to be checked
    } else {
      i++;
    }
  }

  // All elements equal to pivot are in [lt..gt] — skip them!
  quickSort3Way(arr, low, lt - 1);
  quickSort3Way(arr, gt + 1, high);
  return arr;
}

console.log(quickSort3Way([4, 2, 4, 1, 4, 3, 4])); // [1, 2, 3, 4, 4, 4, 4]
console.log(quickSort3Way([1, 1, 1, 1]));           // [1, 1, 1, 1] — very fast!

Common Interview Problems

Problem: K-th Largest Element in an Array

This is LeetCode 215 — one of the most frequently asked interview questions.

function findKthLargest(nums, k) {
  // k-th largest = (n-k)-th index in sorted order (0-indexed)
  const target = nums.length - k;

  function partition(left, right) {
    // Randomized pivot to avoid worst case
    const randIdx = Math.floor(Math.random() * (right - left + 1)) + left;
    [nums[randIdx], nums[right]] = [nums[right], nums[randIdx]];

    const pivot = nums[right];
    let storeIdx = left;

    for (let i = left; i < right; i++) {
      if (nums[i] <= pivot) {
        [nums[storeIdx], nums[i]] = [nums[i], nums[storeIdx]];
        storeIdx++;
      }
    }
    [nums[storeIdx], nums[right]] = [nums[right], nums[storeIdx]];
    return storeIdx;
  }

  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const pivotIdx = partition(left, right);
    if (pivotIdx === target) return nums[pivotIdx];
    else if (pivotIdx < target) left = pivotIdx + 1;
    else right = pivotIdx - 1;
  }
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));             // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4));   // 4

Problem: Sort Colors (Dutch National Flag)

This is LeetCode 75 — sort an array of 0s, 1s, and 2s in-place:

function sortColors(nums) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 2) {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    } else {
      mid++;
    }
  }
  return nums;
}

console.log(sortColors([2, 0, 2, 1, 1, 0])); // [0, 0, 1, 1, 2, 2]

QuickSort vs Other Sorting Algorithms

Property	QuickSort	MergeSort	HeapSort
Average Time	O(n log n)	O(n log n)	O(n log n)
Worst Time	O(n²)	O(n log n)	O(n log n)
Space	O(log n)	O(n)	O(1)
Stable	No	Yes	No
Cache-friendly	Yes	Less so	No
In-place	Yes	No	Yes

Why is QuickSort often faster in practice despite the same Big-O? Cache locality. QuickSort accesses memory sequentially within partitions, while HeapSort jumps around the array, and MergeSort copies data to auxiliary arrays.

When to Use QuickSort vs QuickSelect

Best Practices

1. Always randomize your pivot: A fixed pivot strategy (first or last element) makes your algorithm vulnerable to adversarial or pre-sorted inputs, turning O(n log n) into O(n²).

2. Use three-way partition for arrays with many duplicates: The Dutch National Flag partition skips over elements equal to the pivot, dramatically improving performance when there are repeated values.

3. Switch to insertion sort for small sub-arrays: When the sub-array has fewer than 10–15 elements, the overhead of recursion outweighs the benefit. Production implementations (like Java's Arrays.sort) do this.

4. Prefer QuickSelect over sorting for k-th element problems: If you only need one element's position, sorting the entire array wastes work. QuickSelect's O(n) average crushes O(n log n).

5. Be cautious of worst-case in interviews: If an interviewer asks about worst-case guarantees, mention that Intro Sort (QuickSort that falls back to HeapSort after too much recursion) gives O(n log n) guaranteed while keeping QuickSort's practical speed.

6. Use iterative QuickSelect in production: The iterative version avoids stack overflow on very large arrays and is just as readable.

7. Remember QuickSort is not stable: If you need to preserve the relative order of equal elements, use MergeSort instead. This matters when sorting objects by one field while preserving earlier orderings.

8. Understand the space complexity: QuickSort's O(log n) average space comes from the recursion stack. Tail-call optimization (always recurring on the smaller partition first) guarantees this bound.

Related Concepts

• Merge Sort — The other divide-and-conquer sorting algorithm; stable and with guaranteed O(n log n) but uses extra space
• Heaps — A Heap-based approach (priority queue) is the main alternative to QuickSelect for k-th element problems, with O(n log k) time
• Binary Search — Shares the divide-and-conquer spirit; QuickSelect is sometimes called "partition-based binary search"
• Divide and Conquer — The general algorithmic paradigm that QuickSort exemplifies
• Counting Sort and Radix Sort — Non-comparison sorts that beat O(n log n) when element ranges are constrained

Practice Problems

These problems are perfect for solidifying your understanding of partitioning, QuickSort, and QuickSelect:

Problem	Platform	Key Concept
Kth Largest Element in an Array	LeetCode 215	QuickSelect
Sort Colors	LeetCode 75	Three-way partition
Top K Frequent Elements	LeetCode 347	QuickSelect variant
K Closest Points to Origin	LeetCode 973	QuickSelect with custom comparator
Wiggle Sort II	LeetCode 324	QuickSelect + 3-way partition
Quicksort 1 - Partition	HackerRank	Basic partition
Quicksort 2 - Sorting	HackerRank	Full QuickSort
Find the Running Median	HackerRank	Related selection problem

Start with the HackerRank partition problems to build intuition, then move to the LeetCode problems where QuickSelect shines as an optimization over sorting.