Quick Sort

1. Choose any pivot element within the array.
2. Transform the array so that all elements smaller than the pivot element is in its left, and all elements larger than the pivot is in its right.
3. Recursively call quicksort on the subarray left and right of the pivot element

Tip

The idea is that once an array is formed like step 2, then the pivot variable is in the correct location once sorted.

https://visualgo.net/en/sorting chooses the pivot variable to be the left-most element. Bro Code’s video chooses right-most element.

Implementation

class QuickSort(Sort[int]):
    def sort(self, array: list[int]) -> list[int]:
        if len(array) < 2:
            return array
        # INVARIANT: `array` has at least 2 elements
 
        # NOTE: 
        # i-1: Right-most index of elements smaller than pivot element
        # j: Element to check
        pivot_idx = len(array) // 2
        pivot = array[pivot_idx]
 
        array = array[:pivot_idx] + array[pivot_idx+1:]
        left = [e for e in array if e <= pivot]
        right = [e for e in array if e > pivot]
        # INVARIANT: All elements in `left` subarray are smaller than `pivot`
        # INVARIANT: All elements in `right` subarray are larger than `pivot`
 
        return self.sort(left) + [pivot] + self.sort(right)