Quick Sort: The Fast but Prickly Genius

Chris was impressed by the speed (O(N log N)) of Merge Sort, but one complaint remained.

"It's fast, but it constantly creates new arrays (slice), using too much memory. Is there an algorithm that keeps the speed but doesn't use extra memory space?"

At that moment, the Senior Developer spoke up.

"That's why Quick Sort is used heavily in practice. This guy is a genius that lives up to its name. It's the fastest on average. But it has a bit of a prickly personality, so you have to handle it with care."

What on earth makes it 'prickly'? Today, we dig into Quick Sort, the standard of sorting algorithms and the most widely used one.

1. Pivot: "Gather Around Me!"

If Merge Sort's philosophy is "Split in half first, sort (merge) later,"

Quick Sort's philosophy is "Pick a standard (Pivot), and shove everything smaller to the left and everything larger to the right."

Operational Process

Let's assume we have an array [5, 2, 1, 8, 4, 7, 6, 3].

2. Implementing in JavaScript (In-place)

The true value of Quick Sort lies in using almost no additional memory (In-place) and just swapping positions within the original array. To do this, we first create a 'Partition Helper' function.

1) Partition Function

This function herds values smaller than the pivot to the left and returns the final index where the pivot should be located.

function pivot(arr, start = 0, end = arr.length - 1) {
  // For convenience, set the first element as the pivot
  let pivotValue = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivotValue > arr[i]) {
      swapIdx++;
      // If we find a value smaller than the pivot, swap it with the value at swapIdx
      // effectively pulling it forward.
      [arr[swapIdx], arr[i]] = [arr[i], arr[swapIdx]];
    }
  }

  // Finally, move the pivot to its real position (swapIdx).
  [arr[start], arr[swapIdx]] = [arr[swapIdx], arr[start]];
  
  return swapIdx; // Return the final index of the pivot
}

2) QuickSort Function

Now, we complete the entire logic using recursion.

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 1. Put the pivot in its place and get that index.
    let pivotIndex = pivot(arr, left, right);

    // 2. Sort the left side of the pivot
    quickSort(arr, left, pivotIndex - 1);

    // 3. Sort the right side of the pivot
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

quickSort([4, 8, 2, 1, 5, 7, 6, 3]);

3. Performance Analysis: Why a "Prickly Genius"?

Pros: The Average Speed King (O(N log N))

It achieves O(N log N) speed like Merge Sort.

However, in reality, it is slightly faster than Merge Sort. This is because there is no overhead of creating new arrays (slice), and accessing adjacent indices is advantageous for computer hardware structures (Cache Locality).

Cons: The Worst Case Scenario (O(N^2))

This is why Quick Sort is 'prickly'.

What happens if we pick the first element (1) as the pivot for an already sorted array [1, 2, 3, 4, 5]?

The array doesn't get split in half; it only shrinks by one element at a time. In this case, the depth becomes N, making it as slow as Bubble Sort (O(N^2)).

4. Merge Sort vs. Quick Sort Comparison

Key Takeaways

All the sorting methods we've learned so far sorted data by "Comparing" them.

However, using a Tree structure allows you to extract the minimum or maximum values incredibly fast.

Let's meet Heap Sort, an elegant sorting method utilizing a data structure called the Binary Heap.

🔗 References