Computer Science topic: Quick Sort Algorithm (Intermediate sorting algorithm)

Even if it might feel pointless to spend time trying to solve and understand algorithms like Quick Sort -and even more now in AI times-, understanding how things work is more valuable than ever. It’s not about redoing what’s already done—it’s about getting better at problem-solving and appreciating the clever solutions behind the tools we use every day.

Quick Sort is actually pretty interesting once you look closer—it uses recursion, calling itself to break the problem into smaller and smaller pieces. It’s like teaching the algorithm to solve a puzzle by solving mini-puzzles first. Even though you won’t need to write Quick Sort yourself these days, understanding how it works helps you think differently and tackle other challenges in creative ways.

Interesting facts...

• Quick Sort is a prime example of the divide-and-conquer approach. It breaks down a problem (sorting) into smaller sub-proble ms (partitioning the array) and solves each part recursively.
• Despite its name, Quick Sort doesn’t always guarantee the quickest performance (its worst-case time complexity is O(n2)). However, with a good pivot selection strategy, its average-case performance is O(n log n), which makes it one of the fastest general-purpose sorting algorithms.
• Randomly selecting a pivot is often more efficient in practice than some deterministic methods!
• Quick Sort is widely used in real-world applications.
• It was invented in 1960 by British computer scientist Tony Hoare, who was trying to translate between Russian and English on an early computer. He needed a fast sorting algorithm for the translation dictionary. The algorithm is still regarded as one of the greatest contributions to computer science.
• It sorts in place, meaning it rearranges the elements in the same array without requiring additional storage

Lets take a look at it!

This is a simple version of It I took from a computer science course.

const _swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

// Pivot function
function pivot(arr, start = 0, end = arr.length + 1) {
  const pivot = arr[start];
  let swapIdx = start;
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      _swap(arr, swapIdx, i);
    }
  }
  _swap(arr, start, swapIdx);
  return swapIdx;
}

// Main function
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    quickSort(arr, left, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, right);
  }
  return arr;
}        

Pseudo code:

• This algorithm exploits the fact that arrays of 0 or 1 elements are always sorted.
• We first need choose an element in the array to act as a "divider." In our case we choose the first element in the array but there are other strategies. Ideally the pivot should be chosen so that its roughly the median value. As said, For simplicity we'll take always the first element (but this might have some consequences regarding efficiency)
• Partition the Array. Rearrange the array such that: 1) Elements smaller than the pivot are on the left and 2) Elements larger than or equal to the pivot are on the right.
• Recursively repeat the operation until the condition left < right is met.

The pivot helper function in the Quick Sort algorithm is a crucial component that rearranges the array around a pivot element. It does everything in-place, that means directly modifying the array without creating new ones. This makes this algorithm efficient in terms of space complexity.

Before the example, lets see it's BIG O Complexity:

Time complexity:

• Best of cases: O(n log n)
• Worst of cases, when our array is already sorted and we are taking always the first element: O(n**2)
• Avergage: O(n log n)

Space complexity:

• Always: O(log n)

Step by step example

Let's try to understand how does it work with an example. You can take a look at the solution to follow the steps.

Lets say we have this array:

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

Initial setup:

• Array: [4, 8, 2, 1, 5, 7, 6, 3]
• Pivot: 4 (the first element is chosen as the pivot).
• Swap Index (swapIdx): 0 (initially set to the same index as the pivot).

Steps:

Get the Pivot index. This means, what is the index of our pivot in the array. The first call, will be over the entire array, then it will be done in "parts".

We will iterate through the array starting from index 1 (element after the pivot) and compare each element with the pivot (4).

1. First iteration

Current Element: 8 (at index 1)
Comparison: Is 8 < 4?
No, so we skip this element.
Array (unchanged): `[4, 8, 2, 1, 5, 7, 6, 3]`
`swapIdx` remains: 0.        

2. Second iteration

Current Element: 2 (at index 2)
Comparison: Is 2 < 4?
Yes, so we:
Increment swapIdx to 1.
Swap `arr[swapIdx]` and `arr[2]` (swap 8 and 2).
Array (after swapping): `[4, 2, 8, 1, 5, 7, 6, 3]`
`swapIdx` becomes: 1.        

3. Third iteration

Current Element: 1 (at index 3)
Comparison: Is 1 < 4?
Yes, so we:
Increment swapIdx to 2.
Swap `arr[swapIdx]` and `arr[3]` (swap 8 and 1).
Array (after swapping): `[4, 2, 1, 8, 5, 7, 6, 3]`
`swapIdx` becomes: 2.        

4. Fourth iteration

Current Element: 5 (at index 4)
Comparison: Is 5 < 4?
No, so we skip this element.
Array (unchanged): `[4, 2, 1, 8, 5, 7, 6, 3]`
`swapIdx` remains: 2.        

5. Fifth iteration

Current Element: 7 (at index 5)
Comparison: Is 7 < 4?
No, so we skip this element.
Array (unchanged): `[4, 2, 1, 8, 5, 7, 6, 3]`
`swapIdx` remains: 2.        

6. Sixth iteration

Current Element: 6 (at index 6)
Comparison: Is 6 < 4?
No, so we skip this element.
Array (unchanged): `[4, 2, 1, 8, 5, 7, 6, 3]`
`swapIdx` remains: 2.        

7. Seventh iteration

Current Element: 3 (at index 7)
Comparison: Is 3 < 4?
Yes, so we:
Increment swapIdx to 3.
Swap `arr[swapIdx` and `arr[7]` (swap 8 and 3).
Array (after swapping): `[4, 2, 1, 3, 5, 7, 6, 8]`
`swapIdx` becomes: 3.        

8. Final step, of the very first call of the function: Swap pivot with swapIdx

Swap `arr[0]` (pivot) with `arr[3]` (swapIdx).
Array (after final swap): `[3, 2, 1, 4, 5, 7, 6, 8]`.        

** The pivot (4) is now correctly positioned at index 3. Pivot Index Returned: `3`.

In this moment we have chosen the pivot and we are standing in this part of the function:

let pivotIdx = pivot(arr, left, right);        

Now we will split the array using our pivot into two parts: left and right. The quickSort function will be called again with each of these arrays:

Left side:

// Right = 2
// Left = 0
// original array [3, 2, 1, 4, 5, 7, 6, 8]
// splitted array [3, 2, 1]
quickSort(arr, left, pivotIdx - 1);  => Left sub-array        

Right side:

// Right = 7
// Left = 4
// splitted array [5, 6, 7, 8]
quickSort(arr, pivotIdx  + 1, right) => Right sub-array        

Recursion ensures that every pivot is placed in its correct position, and smaller and larger elements are sorted within their subarrays. By dividing the problem into smaller parts, the algorithm gradually sorts the entire array. The array is being sorted in place, meaning all the sorting happens within the same array without creating new arrays for left and right subarrays. This is one of the reasons why Quick Sort is efficient in terms of memory usage.

Hope you enjoyed it as much as I did! If you have any suggestions, spotted a mistake, or just want to share your thoughts, feel free to leave a comment below!.