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


AliExpress RU&CIS

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: «Три алгоритма поиска шаблона в тексте».



Введение


Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе «Алгоритмы и структуры данных» дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи


Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

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


В прошлый раз мы поговорили о чуть более сложной сортировке — сортировке вставками. Сегодня речь пойдет о существенно более сложном алгоритме — быстрой сортировке (еще ее называют сортировкой Хоара).

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


Алгоритм быстрой сортировки является рекурсивным, поэтому для простоты процедура на вход будет принимать границы участка массива от l включительно и до r не включительно. Понятно, что для того, чтобы отсортировать весь массив, в качестве параметра l надо передать 0, а в качестве r — n, где по традиции n обозначает длину массива.

В основе алгоритма быстрой сортировке лежит процедура partition. Partition выбирает некоторый элемент массива и переставляет элементы участка массива таким образом, чтобы массив разбился на 2 части: левая часть содержит элементы, которые меньше этого элемента, а правая часть содержит элементы, которые больше или равны этого элемента. Такой разделяющий элемент называется пивотом.

Реализация partiion'а:

partition(l, r):
    pivot = a[random(l ... r - 1)]
    m = l
    for i = l ... r - 1:
        if a[i] < pivot:
            swap(a[i], a[m])
            m++
    return m

Пивот в нашем случае выбирается случайным образом. Такой алгоритм называется рандомизированным. На самом деле пивот можно выбирать самым разным образом: либо брать случайный элемент, либо брать первый / последний элемент учаcтка, либо выбирать его каким-то «умным» образом. Выбор пивота является очень важным для итоговой сложности алгоритма сортировки, но об этом несколько позже. Сложность же процедуры partition — O(n), где n = r — l — длина участка.

Теперь используем partition для реализации сортировки:

Реализация partiion'а:

sort(l, r):
    if r - l = 1:
        return
    m = partition(l, r)
    sort(l, m)
    sort(m, r)

Крайний случай — массив из одного элемента обладает свойством упорядоченности. Если массив длинный, то применяем partition и вызываем процедуру рекурсивно для двух половин массива.

Если прогнать написанную сортировку на примере массива 1 2 2, то можно заметить, что она никогда не закончится. Почему так получилось?

При написании partition мы сделали допущение — все элементы массива должны быть уникальны. В противном случае возвращаемое значение m будет равно l и рекурсия никогда не закончится, потому как sort(l, m) будет вызывать sort(l, l) и sort(l, m). Для решения данной проблемы надо массив разделять не на 2 части (< pivot и >= pivot), а на 3 части (< pivot, = pivot, > pivot) и вызывать рекурсивно сортировку для 1-ой и 3-ей частей.

Анализ


Предлагаю проанализировать данный алгоритм.

Временная сложность алгоритма выражается через нее же по формуле: T(n) = n + T(a * n) + T((1 — a) * n). Таким образом, когда мы вызываем сортировку массива из n элементов, тратится порядка n операций на выполнение partition'а и на выполнения себя же 2 раза с параметрами a * n и (1 — a) * n, потому что пивот разделил элемент на доли.

В лучшем случае a = 1 / 2, то есть пивот каждый раз делит участок на две равные части. В таком случае: T(n) = n + 2 * T(n / 2) = n + 2 * (n / 2 + 2 * T(n / 4)) = n + n + 4 * T(n / 4) = n + n + 4 * (n / 4 + 2 * T(n / 8)) = n + n + n + 8 * T(n / 8) =…. Итого будет log(n) слагаемых, потому как слагаемые появляются до тех пор, пока аргумент не уменьшится до 1. В результате T(n) = O(n * log(n)).

В худшем случае a = 1 / n, то есть пивот отсекает ровно один элемент. В первой части массива находится 1 элемент, а во второй n — 1. То есть: T(n) =n + T(1) + T(n — 1) = n + O(1) + T(n — 1) = n + O(1) + (n — 1 + O(1) + T(n — 2)) = O(n^2). Квадрат возникает из-за того, что он фигурирует в формуле суммы арифметической прогрессии, которая появляется в процессе расписывания формулы.

В среднем в идеале надо считать математическое ожидание различных вариантов. Можно показать, что если пивот делит массив в отношении 1:9, то итоговая асимптотика будет все равно O(n * log(n)).

Сортировка называется быстрой, потому что константа, которая скрывается под знаком O на практике оказывается достаточно небольшой, что привело к широкому распространению алгоритма на практике.

Читать ещё






Комментарии (13):

  1. maxzhurkin
    /#22225528 / -1

    Это худшая реклама курса, которую только можно придумать. Любое объяснение должно быть простым и понятным. Это объяснение простое, но не понятное

    P.S.

    Сортировка называется быстрой, потому что константа, которая скрывается под знаком O на практике оказывается достаточно небольшой, что привело к широкому распространению алгоритма на практике.
    под O не константа — константа под O только в одном классе сложности — O(1)

    P.P.S.
    И вообще, нет смысла рассуждать о размере константы под O, потому что O(1) и O(1000000) являются одним и тем же классом сложности

    • rodinvv
      /#22226010 / +4

      f(n) = O(g(n)), если существует номер n0 и константа c > 0 такие, что для любого n начиная с n0 имеет место соотношение: f(n) < c * g(n).

      Это определение О-большого.

      • maxzhurkin
        /#22226070

        В таком случае, термин «константный множитель» подошёл бы больше, но «меряться константами» среди оценок сложности не принято (по этому поводу сказано в P.P.S)

  2. GnuriaN
    /#22225742 / +2

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


    1. Статья на хабре напоминает отписку, а заначит автор так же готовиться к занятиям.
    2. Хабр позволяет форматировать не только текст, но и код, а также вставлять формулы. Ни первого, ни второго, ни третьего нет в статье, а что я тогда увижу в презентации к уроку?
    3. Объяснение на пальцах! Вот за этим идут на курсы и идут не только те, кто хотят получить новые знания, но и те, кто хочет структурировать имеющуюся информацию.
    4. На удивление у ваших конкурентов и то лучше расписан сам алгоритм.
    5. Быстрый поиск выдал еще две хорошие статьи на эту тему.

    Вот зачем мне идти к вам и платить деньги, если мне придётся для понимания опять самому всё искать?


    А ещё не понятно на чём написан код ((((


    sort(l, r):
        if r - l = 1:
            return
        m = partition(l, r)
        sort(l, m)
        sort(m, r)

    Всё сказанное ИМХО (не путать с IMHO).

  3. Mabu
    /#22225952 / +2

    Не пивот, а опорный элемент.

  4. jknight
    /#22226082 / +1

    Когда Хабр из сайта для IT-профессионалов, обсуждающих серьезные и интересные проблемы, стал рекламной площадкой для вайтивайтишных курсов и школьников-умею-в-формы-на-ангуляре-пишу-свой-сайт-на-пхп-и-жабаскрипте?


    Стыдно за него последние несколько лет.


    Статьи вроде этой уже есть на Википедии, и нечего им оттуда переезжать.

  5. Emelian
    /#22226712

    Могу предложить свой собственный алгоритм сортировки: http://emery-emerald.narod.ru/Cpp/2E1562.html. Это куда интересней, чем обсуждать давно известное :).

    • domix32
      /#22228528

      http
      narod ru

      а может не надо? А то потом еще и баннеры после вас лечи

  6. Emelian
    /#22233520

    На TimSort похоже.
    Да, похоже! Я этого не знал.

    Вот, что пишет https://ru.wikipedia.org/wiki/Timsort по этому поводу:

    Основная идея алгоритма

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

    Принципиальные особенности алгоритма в деталях, а именно в алгоритме разделения и модификации сортировки слиянием.

    Да, основные различия в деталях реализации. У меня опубликована рабочая версия, демонстрирующая работу внешней сортировки реального dbf-файла. Кроме этого, вычислена средняя длина упорядоченной подпоследовательности в случайной, равномерно распределенной последовательности (равная 2e – 3) и показана наихудшая (зигзагообразная) последовательность для сортировки этим алгоритмом. Также показана зависимость работы алгоритма от двоичного разложения количества упорядоченных подпоследовательностей в искомой последовательности. У Тима Петерсона этого в явном виде нет, но есть субалгоритм «Галоп», которого нет у меня.

    В общем, я думаю, что используются похожие идеи, отличающиеся в нюансах. Но приоритет за Тимом, поскольку его публикация 2002 года, а моя 2010 (см. также https://www.codeproject.com/Articles/92761/Work-C-Algorithm-of-External-Natural-Merge-Sort-wi)

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