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

Быстрая сортировка (англ. quick sort, сортировка Хоара) — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(n\log{n})[/math], что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из [math]n[/math] элементов в худшем случае может составить [math]\Theta(n^2)[/math], на практике этот алгоритм является одним из самых быстрых.

Алгоритм

• из массива выбирается некоторый опорный элемент [math]A[i][/math].
• запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные [math]A[i][/math], влево от него, а все ключи, большие, либо равные [math]A[i][/math] — вправо.
• для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру..

Псевдокод

  function quicksort(A: int[n], int l, int r):
     if l < r
        q = partition(A, l, r)
        quicksort(A, l, q - 1)
        quicksort(A, q + 1, r)

Для сортировки всего массива необходимо выполнить процедуру [math]\mathrm{quicksort(A, 0, length[A] - 1)}[/math].

Разбиение массива

Основной шаг алгоритма сортировки — процедура [math]\mathrm{partition}[/math], которая переставляет элементы массива [math]A[p..r][/math] нужным образом:

  int partition(A: int[n], int l, int r):
      x = A[l]
      i = l
      j = r
      while true 
          while A[i] < x 
               i = i + 1
          while A[j] > x 
               j = j - 1
          if i < j 
              swap(A[i++], A[j--])
          else 
              return j

Асимптотика

Худшее время работы

Предположим, что мы разбиваем массив так, что одна часть содержит [math]n - 1[/math] элементов, а вторая — [math]1[/math]. Поскольку процедура разбиения занимает время [math]\Theta(n)[/math], для времени работы [math]T(n)[/math] получаем соотношение:

[math]T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)[/math].

Мы видим, что при максимально несбалансированном разбиении время работы составляет [math]\Theta(n^2)[/math]. В частности, это происходит, если массив изначально отсортирован.

Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного

В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает [math]\Theta(n^2)[/math] сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться [math]1[/math], а в другом [math] n - 1 [/math] элемент).

Заполним сначала массив [math]A[/math] длины [math]n[/math] элементами от [math]1[/math] до [math] n [/math], затем применим следующий алгоритм (нумерация с нуля):

  function antiQsort(A: int[n]):
     for i = 0 to n - 1 
        swap(A[i], A[i / 2])

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

При выполнении [math]\mathrm{partition}[/math] делается [math]\Theta(n)[/math] сравнений из-за того, что с помощью индексов [math]i[/math] и [math]j[/math] мы проходим в лучшем случае [math]\Omega(n)[/math] элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае [math]O(2n)[/math] элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура [math]\mathrm{partition}[/math] делает [math]\Theta(n)[/math] сравнений с точностью до константы.

Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. [math]\mathrm{antiQsort}[/math] на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А [math]\mathrm{partition}[/math] делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как [math] \mathrm{antiQsort} [/math] на массиве любой длины будет выполнять операции, обратные [math]\mathrm{partition}[/math]. Фактически, [math]\mathrm{partition}[/math] — это [math]\mathrm{antiQsort}[/math], запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала [math]i[/math] дойдет до середины массива, до опорного элемента, [math]j[/math] останется равным индексу последнего элемента. Затем произойдет [math]\mathrm{swap}[/math] и [math]i[/math] снова начнет увеличиваться, пока не дойдет до последнего элемента, [math]j[/math] опять не изменит свою позицию. Потом произойдет выход из [math]\mathrm{while}[/math].

Разбиение массива будет произведено [math]\Theta(n)[/math] раз, потому что разбиение производится на массивы длины [math]1[/math] и [math] n - 1 [/math] из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется [math]\Theta(n)[/math] [math]\mathrm{partition}[/math] и [math]\Theta(n)[/math] сравнений для каждого выполнения [math]\mathrm{partition}[/math]. Тогда быстрая сортировка выполнит [math]\Theta(n^2)[/math] сравнений для массива, построенного таким способом.

Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента

Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае - [math]\Theta(n^2)[/math]) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной [math]1[/math] и [math]n-1[/math] на каждой итерации. Создадим массив [math]Arr[/math] длины [math]n[/math], заполненный элементами типа [math]pair[/math]. Такой элемент хранит пару значений [math](val, key)[/math], где [math]val[/math] - элемент массива, а [math]key[/math] - индекс. Изначально [math]Arr(i)[/math] элемент имеет вид [math](0, i)[/math].

Далее, запустим для данного массива алгоритм быстрой сортировки. На каждом шаге будем выполнять следующие действия: при обращении к [math]i[/math]-ому элементу в качестве опорного на шаге под номером [math]k[/math], присвоим [math]val(Arr(i)) = n-k+1[/math]. После чего выполним шаг сортировки. После завершения работы алгоритма сортировки, искомым будет являться массив из [math]val(i)[/math], отсортированных по индексам [math]key(i)[/math].

Пример для [math]n = 4[/math], при последовательном выборе опорных элементов [math]2, 2, 1, 1[/math].

Построение массива
Шаг 1.0	Шаг 1.1	Шаг 1.2	Шаг 2.0	Шаг 2.1	Шаг 2.2	Шаг 3.0
1 2 3 4 0 0 0 0	1 2 3 4 0 4 0 0	1 4 3 2 0 0 0 4	1 4 3 2 0 0 0 4	1 4 3 2 0 3 0 4	1 3 4 2 0 0 3 4	1 3 4 2 0 0 3 4
Шаг 3.1	Шаг 3.2	Шаг 4.0	Шаг 4.1	Шаг 4.2	результат
1 3 4 2 2 0 3 4	3 1 4 2 0 2 3 4	3 1 4 2 0 2 3 4	3 1 4 2 1 2 3 4	3 1 4 2 1 2 3 4	1 2 3 4 2 4 1 3
Итоговый массив
2 4 1 3

Почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении [math]Quicksort[/math] алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом, так как каждый раз массив разбивается на две части - большие или равные опорному элементы и меньшие его - на каждом шаге имеем разбиение на массивы длины [math]1[/math] и [math]n-1[/math], чего мы, собственно, и добивались. При таком выполнении алгоритма происходит [math]\Theta(n^2)[/math] разделений на два подмассива, и на каждом разделении выполняется [math]\Theta(n^2)[/math] сравнений. Следовательно, на данном массиве быстрая сортировка работает за [math]\Theta(n^2)[/math].

Среднее время работы

Лемма:

Время работы алгоритма быстрой сортировки равно [math]O(n \log n)[/math].

Доказательство:

[math]\triangleright[/math]

Пусть Х — полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений. Переименуем элементы массива как [math]z_1...z_n[/math], где [math]z_i[/math] наименьший по порядку элемент. Также введем множество [math]Z_{ij} = \{z_i, z_{i+1}...z_j\}[/math]. Заметим, что сравнение каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении. Поскольку каждая пара элементов сравнивается не более одного раза, полное количество сравнений выражается как [math]X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}[/math], где [math]X_{ij} = 1[/math] если произошло сравнение [math]z_i[/math] и [math]z_j[/math] и [math]X_{ij} = 0[/math], если сравнения не произошло. Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим [math]E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i[/math] сравнивается с [math]z_j\}[/math] Осталось вычислить величину [math]Pr\{z_i[/math] сравнивается с [math]z_j\}[/math] — вероятность того, что [math]z_i[/math] сравнивается с [math]z_j[/math]. Поскольку предполагается, что все элементы в массиве различны, то при выборе [math]x[/math] в качестве опорного элемента впоследствии не будут сравниваться никакие [math]z_i[/math] и [math]z_j[/math] для которых [math]z_i \lt x \lt z_j[/math]. С другой стороны, если [math]z_i[/math] выбран в качестве опорного, то он будет сравниваться с каждым элементом [math]Z_{ij}[/math] кроме себя самого. Таким образом элементы [math]z_i[/math] и [math]z_j[/math] сравниваются тогда и только тогда когда первым в множестве [math]Z_{ij}[/math] опорным элементом был выбран один из них. [math]Pr\{z_i[/math] сравнивается с [math]z_j\} = Pr\{[/math]первым опорным элементом был [math]z_i[/math] или [math]z_j\} = Pr\{[/math]первым опорным элементом был [math]z_i\} + Pr\{[/math]первым опорным элементом был [math]z_j\} = \frac {1}{j-i+1} + \frac {1}{j-i+1} = \frac {2}{j-i+1} [/math] [math] E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} \lt \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)[/math]

[math]\triangleleft[/math]

Mатожидание времени работы быстрой сортировки будет [math]O(n \log n)[/math].

Улучшения

В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь [math]O(n)[/math], а время работы алгоритма [math]O(n^2)[/math]. Существуют различные способы разбиения массива, направленные против худшего случая:

• При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — [math]O(n \log n)[/math].
• Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов).
• Разбивать массив не на две, а на три части.

Оптимизация глубины рекурсии до O(logn) в худшем случае

Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит [math]\log n[/math], а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.

Источники информации

• Википедия — быстрая сортировка
• Wikipedia — Quicksort
• Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7