Quick Sort

• Divide and conquer algo
• Worst Case: $O(n^2)$
• Despite $O(n^2)$ considered faster:
  • in place
  • cache friendly
  • Avg $O(n log n)$
  • tail recursive

Array partition

Choose 1 element (pivot) and bring all smaller elements on left and larger on right.

2 partition algorithm:

• Lomuto
• Hoare's

Lumoto Partition

• Last element - r (right) - pivot
• picks the last element - places it at the correct position and return the position

Python

def lumotoPartition(arr, l, r):
    pivot = arr[r]
    i = l - 1
    for j in range(l, r):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i

Hoare's Partition

• First element - l (left) - pivot
• picks the first element - places it at the correct position and returns the position
• Faster than Lumoto

Python

def hoaresPartition(arr, l, r):
    pivot = arr[l]
    i, j = l - 1, r + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

Quick Sort

Python

# LUMOTO
def quickSort(arr, l, h):
    if l < h:
        pivot = lumotoPartition(arr, l, h)
        quickSort(arr, l, pivot - 1)
        quickSort(arr, pivot + 1, h)

# HOARES
def quickSort(arr, l, h):
    if l < h:
        pivot = hoaresPartition(arr, l, h)
        quickSort(arr, l, pivot)
        quickSort(arr, pivot + 1, h)