Подробное описание алгоритма быстрой сортировки

quick_sort.py

def _partition(nums: list, first: int, last: int) -> int:
    """
    Выбираем опорный элемент.
    Используем схему Хоара, так как она использует меньше перестановок
    """
    pivot = nums[(first + last) // 2]  # Предварительно в качестве опорного выбираем средний элемент массива
    i = first - 1  # задаём курсоры поиска индексами первого и последнего элемента входного массива,
    j = last + 1  # смещёнными на одну позицию за границы массива, для компенсации последующего движения в цикле

    # Двигаемся по левой и правой части массива, по направлению к опорному, сравнивая элементы с опорным,
    # в левой части находим элемент больше опорного, в правой — меньше опорного, меняем их местами,
    # получая массив, где в левой части всё, что меньше опорного, в правой — всё что больше,
    # возвращаем индекс опорного элемента.
    while True:
        i += 1  # сдвигаем левый курсор на одну позицию вправо
        while nums[i] < pivot:  # сравниваем левый элемент с опорным
            i += 1  # и если он меньше опорного, сдвигаем курсор вправо

        j -= 1  # сдвигаем правый курсор на одну позицию вправо
        while nums[j] > pivot:  # сравниваем правый элемент с опорным
            j -= 1  # и если он больше опорного, сдвигаем курсор влево

        if i >= j:  # если курсоры сошлись в одной точке или поменялись местами,
            return j  # прерываем цикл и возвращаем индекс опорного элемента

        nums[i], nums[j] = nums[j], nums[i]  # если же область поиска не нулевая,
        # то меняем правый и левый элемент между собой, теперь у нас элементы больше опорного находятся справа,
        # а элементы меньше опорного — слева.
        # Возвращаемся к действиям выше с изменённым массивом


def qsort(items: list, first: int = 0, last: int = None):
    # Чтобы конечную функцию можно было использовать без указания границ массива и сохранить рекурсию
    if last is None:
        last = len(items) - 1

    # Если заданная область сортировки нулевая, прерываем рекурсию
    if first < last:
        split_index = _partition(items, first, last)  # Находим индекс опорного элемента схемой разбиения Хоара
        qsort(items, first, split_index)  # Выполняем быструю сортировку левой части массива
        qsort(items, split_index + 1, last)  # Выполняем быструю сортировку правой части массива