Быстрая сортировка в Python

Spread the love

Введение

Быстрая сортировка – очень популярный алгоритм сортировки, который часто используется вместе с сортировкой слиянием. Это хороший пример эффективного алгоритма сортировки со средней сложностью O(n logn). Часть его популярности также связана с простотой реализации.

Мы используем пример с простыми целыми числами в первой части этой статьи, но так же приведем пример того, как изменить этот алгоритм для сортировки объектов с пользовательскими классами.

Быстрая сортировка является представителем трех типов алгоритмов сортировки: divide and conquer (разделяй и властвуй), in-place (на месте) и unstable (нестабильный).

  • Divide and conquer: Быстрая сортировка разбивает массив на меньшие массивы до тех пор, пока он не закончится пустым массивом, или массивом, содержащим только один элемент, и затем все рекурсивно соединяется в сортированный большой массив.
  • In place: Быстрая сортировка не создает никаких копий массива или его подмассивов. Однако этот алгоритм требует много стековой памяти для всех рекурсивных вызовов, которые он делает.
  • Unstable: стабильный (stable) алгоритм сортировки – это алгоритм, в котором элементы с одинаковым значением отображаются в том же относительном порядке в отсортированном массиве, что и до сортировки массива. Нестабильный алгоритм сортировки не гарантирует этого, это, конечно, может случиться, но не гарантируется. Это может быть важным, когда вы сортируете объекты вместо примитивных типов. Например, представьте, что у вас есть несколько объектов Person одного и того же возраста, например, Дейва в возрасте 21 года и Майка в возрасте 21 года. Если бы вы использовали Quicksort в коллекции, содержащей Дейва и Майка, отсортированных по возрасту, нет гарантии, что Дейв будет приходить раньше Майка каждый раз, когда вы запускаете алгоритм, и наоборот.

Быстрая сортировка

Базовая версия алгоритма делает следующее:

Разделяет коллекцию на две (примерно) равные части, принимая псевдослучайный элемент и использовать его в качестве опоры (как бы центра деления). Элементы, меньшие, чем опора, перемещаются влево от опоры, а элементы, размер которых больше, чем опора, справа от него. Этот процесс повторяется для коллекции слева от опоры, а также для массива элементов справа от опоры, пока весь массив не будет отсортирован.

Когда мы описываем элементы как «больше» или «меньше», чем другой элемент – это не обязательно означает большие или меньшие целые числа, мы можем отсортировать по любому выбранному нами свойству.

К примеру, если у нас есть пользовательский класс Person, и у каждого человека есть имя и возраст, мы можем сортировать по имени (лексикографически) или по возрасту (по возрастанию или по убыванию).

Как работает Быстрая сортировка

Быстрая сортировка чаще всего не сможет разделить массив на равные части. Это потому, что весь процесс зависит от того, как мы выбираем опорный элемент. Нам нужно выбрать опору так, чтобы она была примерно больше половины элементов и, следовательно, примерно меньше, чем другая половина элементов. Каким бы интуитивным ни казался этот процесс, это очень сложно сделать.

Подумайте об этом на мгновение – как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку – случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

Самый простой подход – просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.

Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.

Теперь, когда мы выбрали опорный элемент – что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем опора, находились слева от него, а все более крупные элементы были справа от него. Меньшие и большие элементы не обязательно будут отсортированы, мы просто хотим, чтобы они находились на правильной стороне оси. Затем мы рекурсивно проходим левую и правую сторону оси.

Рассмотрим пошагово то, что мы планируем сделать, это поможет проиллюстрировать весь процесс. Пусть у нас будет следующий список.

29, 99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44

Выберем первый элемент как опору (29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low), 27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

  • Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

  • Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
  • Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 99.
  • Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

  • Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 99 теперь на своих местах)
  • Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим – 12
  • Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,12,99,44

  • Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,12,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,12,99,44 (правая сторона). И так далее.

Реализация

Сортировка массивов

Быстрая сортировка является естественным рекурсивным алгоритмом – разделите входной массив на меньшие массивы, переместите элементы в нужную сторону оси и повторите.

Давайте рассмотрим, как будут выглядеть несколько рекурсивных вызовов:

  • Когда мы впервые вызываем алгоритм, мы рассматриваем все элементы – от индексов 0 до n-1, где n – количество элементов в нашем массиве.
  • Если бы наш опорный элемент оказался в положении k, мы бы повторили процесс для элементов от 0 до k-1 и от k + 1 до n-1.
  • При сортировке элементов от k + 1 до n-1 текущий опорный элемент окажется в некоторой позиции p. Затем мы отсортируем элементы от k + 1 до p-1 и от p + 1 до n-1 и так далее.

При этом мы будем использовать две функции – partition() и quick_sort(). Функция quick_sort() сначала разделит коллекцию через partition(), а затем рекурсивно вызывает себя для разделенных частей.

Давайте начнем с функции partition():

def partition(array, start, end):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        # Если текущее значение, на которое мы смотрим, больше, чем опорный элемент pivot
        # он в правильном месте (правая сторона pivot), и мы можем двигаться влево, до следующего элемента.
        # Нам также нужно убедиться, что мы не превзошли указатель low, так как
        # он указывает на то, что мы уже переместили все элементы на правильную сторону оси
        while low <= high and array[high] >= pivot:
            high = high - 1

        # Противоположный процесс вышеупомянутого
        while low <= high and array[low] <= pivot:
            low = low + 1

        # Мы либо нашли значение для максимума и минимума,
        # или low выше, чем high, и в этом случае мы выходим из цикла
        if low <= high:
            array[low], array[high] = array[high], array[low]
            # Цикл продолжается
        else:
            # Выходим из цикла
            break

    array[start], array[high] = array[high], array[start]

    return high

И, наконец, давайте реализуем функцию quick_sort():

def quick_sort(array, start, end):
    if start >= end:
        return

    p = partition(array, start, end)
    quick_sort(array, start, p-1)
    quick_sort(array, p+1, end)

После того, как обе функции реализованы, мы можем запустить quick_sort():

array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]

quick_sort(array, 0, len(array) - 1)
print(array)

Результат:

[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]

Поскольку алгоритм unstable (нестабилен), нет никакой гарантии, что два 44 будут всегда в этом порядке друг за другом. Хотя это ничего не значит для массива целых чисел.

Сортировка пользовательских объектов

Есть несколько способов переписать этот алгоритм для сортировки пользовательских объектов в Python. Очень Pythonic способ был бы реализовать операторы сравнения для данного класса, что означает, что нам на самом деле не нужно менять реализацию алгоритма, так как >, ==, <= и т. д. также будет работать на нашем объекте класса.

Другой вариант – позволить вызывающей стороне предоставить метод для нашего алгоритма, который затем будет использоваться для фактического сравнения объектов. Переписать алгоритм таким образом для использования с пользовательскими объектами довольно просто. Имейте в виду, однако, что алгоритм будет unstable.

Давайте начнем с класса Person:

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __str__(self):
        return self.name

Это довольно простой класс только с двумя свойствами, именем и возрастом. Мы хотим использовать возраст как наш ключ сортировки, что мы сделаем, предоставив специальную лямбда-функцию для алгоритма сортировки.

Но сначала давайте посмотрим, как эта предоставленная функция используется в алгоритме. Вместо прямого сравнения с операторами <= или> =, вызовем функцию, которая определит, какой объект Person старше по возрасту:

def partition(array, start, end, compare_func):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        while low <= high and compare_fun(array[high], pivot):
            high = high - 1

        while low <= high and not compare_fun(array[low], pivot):
            low = low + 1

        if low <= high:
            array[low], array[high] = array[high], array[low]
        else:
            break

    array[start], array[high] = array[high], array[start]

    return high
def quick_sort(array, start, end, compare_func):
    if start >= end:
        return

    p = partition(array, start, end, compare_func)
    quick_sort(array, start, p-1, compare_func)
    quick_sort(array, p+1, end, compare_func)

А теперь давайте разберем коллекцию этих объектов. Вы можете увидеть, что сравнение объектов предоставляется вызову quick_sort через лямбду, которая выполняет фактическое сравнение свойства age:

p1 = Person("Dave", 21)
p2 = Person("Jane", 58)
p3 = Person("Matthew", 43)
p4 = Person("Mike", 21)
p5 = Person("Tim", 10)

array = [p1,p2,p3,p4,p5]

quick_sort(array, 0, len(array) - 1, lambda x, y: x.age < y.age)
for person in array:
    print(person)

Результат:

Tim
Dave
Mike
Matthew
Jane

Реализуя алгоритм таким образом, он может использоваться с любым произвольным объектом, который мы выберем, при условии, что мы обеспечиваем соответствующую функцию сравнения.

Оптимизация быстрой сортировки

Учитывая, что быстрая сортировка сортирует «половинки» заданного массива независимо друг от друга, это оказывается очень удобным для распараллеливания. У нас может быть отдельный поток, который сортирует каждую «половину» массива, и в идеале мы могли бы вдвое сократить время, необходимое для его сортировки.

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

Для сортировки небольших массивов рекомендуется использовать простой нерекурсивный алгоритм. Даже что-то простое, например сортировка вставкой, будет более эффективным для небольших массивов, чем быстрая сортировка. Поэтому в идеале мы могли бы проверить, имеет ли наш подмассив лишь небольшое количество элементов (большинство рекомендаций говорят о 10 или менее значений), и если да, то мы бы отсортировали его с помощью Insertion Sort (сортировка вставкой).

Популярная разновидность быстрой сортировки – это Multi-Pivot Quicksort, которая разбивает исходный массив на n меньших массивов, используя n-1 Pivots. Однако в большинстве случаев используются только две опоры, не более.

Интересный факт: Dual-pivot Quicksort (двойная сводная быстрая сортировка) вместе с Insertion Sort для небольших массивов использовалась в реализации стандартной сортировки в Java 7.

Заключение

Как мы уже упоминали ранее, эффективность быстрой сортировки сильно зависит от выбора точки опоры – он может «упростить или усложнить» сложность алгоритма во времени (и в пространстве стека). Нестабильность алгоритма также может стать препятствием для использования с пользовательскими объектами.

Тем не менее, несмотря на все это, средняя сложность времени O(n*logn) в быстрой сортировки, а также его относительно небольшое потребление памяти и простая реализация делают его очень эффективным и популярным алгоритмом.

Если вы хотите узнать больше, ознакомьтесь с нашей другой статьей Алгоритмы сортировки в Python (оригинал: Sorting Algorithms in Python), которая охватывает больше алгоритмов сортировки в Python, но не так подробно.

Оригинальная статья Olivera PopovićQuicksort in Python

Была ли вам полезна эта статья?
[0 / 0]

Spread the love

Добавить комментарий

Ваш e-mail не будет опубликован.