Quicksort в Python - pythobyte.com

Вступление

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

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

Quicksort является представителем трех типов алгоритмов сортировки: divide and conquer , in-place и unstable .

Divide and conquer : Quicksort разбивает массив на меньшие массивы до тех пор, пока не получит пустой массив или массив, содержащий только один элемент, а затем рекурсивно сортирует большие массивы.
In place : Quicksort не создает никаких копий массива или его подмассивов. Однако он требует стековой памяти для всех рекурсивных вызовов, которые он делает.
Нестабильный : стабильный алгоритм сортировки-это алгоритм, в котором элементы с одинаковым значением появляются в том же относительном порядке в отсортированном массиве, что и до сортировки массива. нестабильный алгоритм сортировки не гарантирует этого, он может конечно, произойти, но это не гарантировано.

Это то, что становится важным, когда вы сортируете объекты вместо примитивных типов. Например, представьте , что у вас есть несколько объектов Person , которые имеют один и тот же возраст , то есть Дэйв в возрасте 21 года и Майк в возрасте 21 года. Если бы вы использовали Quicksort для коллекции, содержащей как Дэйва, так и Майка, отсортированных по возрасту, нет никакой гарантии, что Дэйв будет приходить раньше Майка каждый раз, когда вы запускаете алгоритм, и наоборот.

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

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

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

Элементы, меньшие, чем ось, перемещаются влево от оси, а элементы, большие, чем ось, – вправо.

Этот процесс повторяется для коллекции слева от оси, а также для массива элементов справа от оси, пока весь массив не будет отсортирован.

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

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

Как Работает Quicksort

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

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

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

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

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

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

Пошаговый взгляд на то, что мы планируем сделать, поможет проиллюстрировать этот процесс. Используя массив, показанный ниже, мы выбрали первый элемент в качестве оси (29), и указатель на меньшие элементы (называемые “низкими”) начинается сразу после этого, а указатель на более крупные элементы (называемые “высокими”) начинается в конце.

29 – это первый пивот, низкий указывает на 99 и высокий указывает на 44

29 | 99 (низкий) ,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21, 44 (высокий)

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

29 | 99 (низкий) ,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12, 21 (высокий) ,44

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

29 | 21 (низкий) ,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12, 99 (высокий) ,44

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

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

29 | 21,27,12,19, 28 (низкий/высокий) ,44,78,87,66,31,76,58,88,83,97,41,99,44

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

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

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

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

Реализация

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

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

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

При первом вызове алгоритма мы рассматриваем все элементы – от индексов 0 to n-1 где n – количество элементов в нашем массиве.
Если бы наш стержень оказался в позиции k , мы бы тогда повторили этот процесс для элементов из 0 к к-1 и от к+1 к н-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:
        # If the current value we're looking at is larger than the pivot
        # it's in the right place (right side of pivot) and we can move left,
        # to the next element.
        # We also need to make sure we haven't surpassed the low pointer, since that
        # indicates we have already moved all the elements to their correct side of the pivot
        while low <= high and array[high] >= pivot:
            high = high - 1

        # Opposite process of the one above
        while low <= high and array[low] <= pivot:
            low = low + 1

        # We either found a value for both high and low that is out of order
        # or low is higher than high, in which case we exit the loop
        if low <= high:
            array[low], array[high] = array[high], array[low]
            # The loop continues
        else:
            # We exit out of the loop
            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]

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

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

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

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

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

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

    def __str__(self):
        return self.name

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

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

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

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

        while low <= high and not compare_func(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

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

Оптимизация Quicksort

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

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

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

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

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

Вывод

Как мы уже упоминали ранее, эффективность Quicksort сильно зависит от выбора pivot – он может “сделать или сломать” временную сложность алгоритма (и пространство стека). Нестабильность алгоритма-это также то, что может нарушить сделку при использовании пользовательских объектов.

Однако, несмотря на все это, средняя временная сложность Quicksort O(n*log _n ) и его относительно низкое использование пространства и простая реализация делают его очень эффективным и популярным алгоритмом.

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