Quicksort

Quicksort is a sorting algorithm using recursion. It works by selecting a value in the array (in the following examples it's the last one) and using it as a pivot, against which all others values are sorted compared and then moved to its left or right depending if they are smaller or bigger.

Once this weak sort has been executed, the two parts before and after the pivot are copied to new arrays, and the process of selecting a pivot, comparing and copying starts again, until eventually each array has only one value, which means it is sorted.

After that, all values are retrieved, and the array is completely sorted.

Example with an array of 16 values:

                        [0-15]
            --------------8--------------
            |                           |
          [1-7]                       [9-15]
     -------4-------             -------12--------
     |             |             |               |
   [1-3]         [5-7]         [9-11]         [13-15]
  ---2---       ---6---       ---2----       ----14---
  |     |       |     |       |      |       |       |
[1-1] [3-3]   [5-5] [7-7]   [9-9] [11-11] [13-13] [15-15]

The big O of Quicksort is O(log n), where log is the number of times a new split is made using the pivot.

But there's a catch: Quicksort doesn't always sort quickly. There are some specific cases that can make the algorithm have terrible for performance.

Among them, it can happen in a reversed sorted array, as it means the last item is the smallest, and that all reversed values will be placed at its right, resulting in a new array for all the remaining values at each iteration.

[6,5,4,3,2,1]
      1---------
               |
          [2,6,5,4,3]
               2-------
                      |
                 [3,6,5,4,3]
                      3-----
                           |
                         // etc...

The solution to avoid this is to always pick the middle element of the array as the pivot.

• If it's sorted, zero swaps will happen.
• If it's reverse sorted, the array will be perfectly split in the middle.
• If it's randomly sorted, then the algorithm has a random chance of being near the middle value.

Knowing this, Quicksort big O is then somewhere between O(log n) best case and O(n²) worst case.

Example:

// Does the weak sort and returns the pivot
function partition(arr: number[], lo: number, hi:number): number {
 
    const pivot = arr[hi]; // Taking the last item as the pivot
    let idx = lo - 1; // Setting the index outside the array
 
    for(let i = lo; i < hi; ++i) {
        if (arr[hi] <= pivot) {
            // Set index position, then swap the values
            idx++;
            const tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
    }
 
    idx++; // Increment the index
 
    // Move the pivot to the index
    arr[hi] = arr[idx];
    arr[idx] = pivot;
 
    return idx;
}
 
function qs(arr: number[], lo: number, hi:number): void {
    if (lo >= hi) {
        return;
    }
 
    const pivotIdx = partition(arr, lo, hi);
    qs(arr, lo, pivotIdx -1);
    as(arr, pivotIdx + 1, hi);
}
 
export default function quick_sort(arr: number[]): void {
    qs(arr, 0, arr.length -1);
}