Quick Sort Algorithm in DSA Javascript

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a pile of books by picking one book as a reference, then putting all smaller books on one side and bigger books on the other, and repeating this for each side until all books are in order.

Array: [7, 2, 5, 3, 9]
Pivot chosen: 5
Partitioned: [2, 3] -> 5 -> [7, 9]

Dry Run Walkthrough

Input: array: [7, 2, 5, 3, 9]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot 9 (last element), partition array

[7, 2, 5, 3, 9]

Why: Pivot divides array into smaller and bigger parts

Step 2: Partition around 9: all elements less than 9 stay left

[7, 2, 5, 3, 9]

Why: All elements are less than 9, so 9 is placed at the end

Step 3: Recursively quick sort left part [7, 2, 5, 3]

[7, 2, 5, 3]

Why: Sort smaller part to fully sort array

Step 4: Choose pivot 3, partition [7, 2, 5, 3]

[7, 2, 5, 3]

Why: Pivot 3 separates smaller and bigger elements

Step 5: Partition around 3: elements less than 3 to left

[2] -> 3 -> [5, 7]

Why: 2 is less than 3, 5 and 7 are greater

Step 6: Recursively quick sort right part [5, 7]

[5, 7]

Why: Sort remaining unsorted part

Step 7: Choose pivot 7, partition [5, 7]

[5, 7]

Why: Pivot 7 separates smaller and bigger elements

Step 8: Partition around 7: 5 is smaller, so 7 placed after 5

[5] -> 7

Why: 5 is smaller than 7, so placed before

Step 9: Combine all parts: [2, 3, 5, 7, 9]

[2, 3, 5, 7, 9]

Why: All parts sorted and combined

Result:

2 -> 3 -> 5 -> 7 -> 9

Annotated Code

DSA Javascript

class QuickSort {
  static partition(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;
  }

  static quickSort(arr, low, high) {
    if (low < high) {
      const pi = QuickSort.partition(arr, low, high);
      QuickSort.quickSort(arr, low, pi - 1);
      QuickSort.quickSort(arr, pi + 1, high);
    }
  }
}

const arr = [7, 2, 5, 3, 9];
QuickSort.quickSort(arr, 0, arr.length - 1);
console.log(arr.join(' -> '));

const pivot = arr[high];

Select pivot as last element to divide array

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

Partition elements: move smaller or equal elements to left side

swap arr[i + 1] and arr[high]; return i + 1;

Place pivot in correct sorted position

if (low < high) { quickSort left part; quickSort right part; }

Recursively sort subarrays around pivot

Output

2 -> 3 -> 5 -> 7 -> 9

Complexity Analysis

Time: O(n log n) average case because the array is divided roughly in half each time and each element is compared once per level

Space: O(log n) due to recursive call stack depth in average case

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it reduces problem size quickly by partitioning

Edge Cases

empty array

No sorting needed, returns immediately

DSA Javascript

if (low < high) {

array with one element

No sorting needed, returns immediately

DSA Javascript

if (low < high) {

array with all equal elements

Partitions but no swaps needed, returns sorted array

DSA Javascript

if (arr[j] <= pivot) {

When to Use This Pattern

When you need to sort an array efficiently by dividing and conquering, look for Quick Sort pattern because it sorts by partitioning around pivots.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping pivot to correct position
Fix: Always select pivot as last element and swap it to its correct place after partitioning

Mistake: Not updating pointers correctly during partition
Fix: Increment i only when swapping smaller elements to left

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you want an efficient average-case sorting algorithm for arrays.

The key insight is partitioning the array around a pivot so smaller elements go left and bigger go right.