Алгоритм быстрой сортировки

Встроенные функции сортировки во многих языках программирования используют именно модификации алгоритма быстрой сортировки, так что можно смело сказать, что это база, которую нужно знать.
Данный алгоритм придумал Чарльз Хоара, поэтому иногда эту сортировку называют сортировкой Хоара.

def quicksort(numbers):
    if len(numbers) < 2:
        return numbers
    pivot = numbers[len(numbers) // 2]

    less = [number for number in numbers if number < pivot]
    equal = [pivot] * numbers.count(pivot)
    greater = [number for number in numbers if number > pivot]
    return quicksort(less) + equal + quicksort(greater)

numbers = [1, 2, 5, 4, 4, 3, 3]

quicksort(numbers) #returns [1, 2, 3, 3, 4, 4, 5]

Замысел здесь в том, что мы выбираем некий опорный элемент и разбиваем массив на три части:

1. В левую часть мы складываем числа, которые меньше опорного;
2. В середену кладем числа равные опорному элементу;
3. А в правую часть — числа, которые больше опорного элемента.

А если всегда выбирать случайное числа в качестве опорного элемента, то быстрая сортировка будет в среднем завершаться за время O(n log n).
Модифицируем немного исходный код:

import random

def quicksort(numbers):
    if len(numbers) < 2:
        return numbers
    pivot = random.choice(numbers)

    less = [number for number in numbers if number < pivot]
    equal = [pivot] * numbers.count(pivot)
    greater = [number for number in numbers if number > pivot]
    return quicksort(less) + equal + quicksort(greater)

numbers = [1, 2, 5, 4, 4, 3, 3]

quicksort(numbers) #returns [1, 2, 3, 3, 4, 4, 5]

Итак, в худшем случае алгоритм будет отрабатывать за O(n²), но в среднем и лучшем случае он отработает за время O(n log n).

Стоит отметить, что данный алгоритм не является оптимальным с точки зрения затрачиваемой памяти, поэтому стоит рассмотреть быструю сортировку «на месте» (in-place quick sort).

In-place quick sort

Так как предыдущий алгоритм быстрой сортировки использует дополнительные массивы, то соответственно расходуется и больше оперативной памяти. И чтобы этого избежать нужно сортировать числа в исходном списке. Для этого нам нужно создать два указателя и сдвигать их в сторону опорного элемента в цикле, переставляя числа.

numbers = [1, 2, 5, 4, 4, 3, 3]

def quicksort(numbers, start, end):
    if start >= end:
        return None

    i, j = start, end
    pivot = numbers[(start + end) // 2]

    while i <= j:
        while numbers[i] < pivot:
            i += 1
        while numbers[j] > pivot:
            j -= 1
        if i <= j:
            numbers[i], numbers[j] = numbers[j], numbers[i]
            i, j = i + 1, j - 1
    quicksort(numbers, start, j)
    quicksort(numbers, i, end)
    return numbers

quicksort(numbers, 0, len(numbers)-1) #returns [1, 2, 3, 3, 4, 4, 5]