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

Алгоритм быстрой сортировки, как и алгоритм слиянием, относят к алгоритмам «разделяй и властвуй». Однако в отличие от последнего он не требует дополнительной памяти и чрезвычайно эффективен при правильной конфигурации. Давайте рассмотрим особенности его работы и реализации.

Описание алгоритма

Быстрая сортировка начинается при разбиении списка (массива) и выборе одного из элементов списка в качестве опорного. Далее остальные элементы передвигаются таким образом, чтобы опорный элемент встал на своё место. Причём те элементы, которые меньше его, перемещаются влево, а те, которые больше либо равны, — вправо.

Реализация алгоритма быстрой сортировки

Есть множество вариаций данного метода. Рассмотрим способ разбиения массива, соответствующий схеме Хоара, — создателя алгоритма быстрой сортировки.

def partition(nums, low, high):  
    # В качестве опорного выбирается средний элемент 
    # В качестве опорного возможен выбор первого, последнего
    # либо произвольного элемента 
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1

        j -= 1
        while nums[j] > pivot:
            j -= 1

        if i >= j:
            return j

        # Когда элемент с индексом i (слева от опорного) больше, чем
        # элемент с индексом j (справа от опорного), мы меняем элементы местами
        nums[i], nums[j] = nums[j], nums[i]

def quick_sort(nums):  
    # Создаём вспомогательную функцию, вызываемую рекурсивно
    def _quick_sort(items, low, high):
        if low < high:
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)

    _quick_sort(nums, 0, len(nums) - 1)

# Проверка, что всё работает
random_list_of_nums = [22, 5, 1, 18, 99]  
quick_sort(random_list_of_nums)  
print(random_list_of_nums) 

Время выполнения алгоритма

Как правило, время выполнения составляет O(n log n).

Примечание: алгоритм быстрой сортировки станет работать медленно, если опорный элемент будет равен наименьшему либо наибольшему элементу списка (массива).

Источник