Рассмотрим методы сортировок, основными операциями в которых является обмен элементов. Да, эта та самая операция swap.

Наверное, самый очевидный метод сортировки — сравнивать ключи $K_i$ и $K_j$, и, если $K_i > K_j$, поменять местами записи $R_i$ и $R_j$. Такой операцией мы последовательно устраняем инверсии в перестановке. Значит в какой-то момент мы дойдем до перестановки без инверсий. Это и будет наш отсортированный массив.

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

Если $b_1, b_2, \dotsc, b_n$ — таблица инверсий исходной перестановки $\sigma_1, \sigma_2, \dotsc, \sigma_n$, то

где $c_j$ — значение $\code{bound} - 1$ перед началом $j$-го прохода.

После $t$ проходов сортировки значение переменной bound будет равно

Их этого факта получаем, что

Анализ распределения $S$ — количества обменов

Значение $S = b_1 + b_2 + \dotsb + b_n$ равно числу инверсий в перестановке $\sigma_1, \sigma_2, \dotsc, \sigma_n$. Распределение числа инверсий мы знаем, его параметры

Анализ распределения $A$ — количества проходов

Вероятность того, что нам потребуется не более $k$ проходов, равна произведению $1/n!$ и числа таблиц инверсий, не содержащих компонент равных $k$ или больше.

Значит вероятность того, что нам потребуется ровно $k$ проходов равна

Среднее значение вычисляем просто по формуле математического ожидания, выполнив суммирование по частям

Величина $P(n)$ подробно анализировалась в разделе «Факториальные суммы» статьи «Асимптотика». Нам достаточно асимптотического поведения $P(n) = \sqrt{\pi n/2} - 2/3 + O(1/\sqrt{n})$.

В итоге получаем, что

Теперь посчитаем дисперсию

Подставляем асимптотическое выражение для $P(n)$ и получаем

Теперь можно вычислить стандартное отклонение

Получаем результат анализа распределения $A$ — количества проходов при сортировке пузырьком

Анализ распределения $C$ — количества сравнений.

Итак, нам нужно проанализировать величину $C = c_1 + c_2 + \dotsb + c_A$, где $c_j = \max\limits~ \{ b_i + i \mid \forall\, b_i \ge j - 1 \} - j$. Пусть $f_j (k)$ — число таких таблиц инверсий $b_1, b_2, \dotsc, b_n$, для которых при $1 \le i \le n$ либо $b_i < j-1$, либо $b_i + i - j \le k$.

Тогда вероятность того, что количество сравнений $c_j$ будет не больше $k$ выражается через $f_j (k)$

Значит вероятность того, что количество сравнений $c_j$ будет в точности $k$ равна

Для вычисления среднего числа сравнений на шаге $j$ посчитаем математическое ожидание

Просуммировав по частям, получаем, что

Тогда, суммируя по $j$, получаем математическое ожидание общего числа сравнений

Теперь можно посчитать дисперсию. Начнем с $c_j$

Сортировка пузырьком, конечно, рабочая, но она относительно медленная. В процессе сортировки пузырьком совершается довольно много лишних сравнений, и элемент не может за один проход переместиться более чем на $1$ позицию, поэтому если наименьший элемент будет самым крайним, то нам потребуется максимальное количество сравнений.

Все эти особенности процесса сортировки пузырьком наталкивают на мысли о сортировке, которая будет чередовать направления прохода по массиву. Кеннет Айверсон в 1962 году сделал интересное наблюдение: если две записи $R_j$ и $R_{j+1}$ не поменялись местами при двух последовательных проходах в обоих направлениях, то они уже стоят на своих местах и их можно исключить из дальнейшего рассмотрения.

Пусть снова $b_1, b_2, \dotsc, b_n$ — таблица инверсий исходной перестановки $\sigma_1, \sigma_2, \dotsc, \sigma_n$. Считаем величины $A$ — количество проходов, $S$ — количество обменов и $C$ — количество сравнений.

где $c_j$ — значение $2 \cdot (\code{right\_bound} - \code{left\_bound})$ перед началом $j$-го прохода.

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

В 1964 году Кеннет Бетчер открыл интересный способ организации сравнений, который позволяет значительно ускорить сортировку и даёт возможность её параллелить.

Алгоритм будет работать для $n \ge 2$.

Вычислим $t = \lceil \log_2 n \rceil$ — наименьшее такое целое число, для которого $2^t \ge n$.

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

Попробуем отказаться от оптимизаций под параллельные алгоритмы в пользу более быстрой сортировки на обычных процессорах с последовательным выполнением операций. Иными словами, новый метод не будет применим для параллельных вычислений, как сортировка Бетчера, но сможет превзойти её на классической однопоточной архитектуре.

Давайте брать одну из записей и сразу двигать её на то место, которое она должна занять после сортировки. Для поиска номера $s$, под которым должна оказаться выбранная запись $R$, нам нужно распределить остальные записи так, чтобы слева от записи $R$ оказались только записи с меньшим ключом, а справа от записи $R$ оказались только записи с большим ключом.

После этой операции у нас получатся два подмассива $R_1, R_2, \dotsc, R_{s-1}$ и $R_{s+1}, R_{s+2}, \dotsc, R_{n}$. При этом, если $K$ — ключ записи $R$, и $K_j$ — ключ записи $R_j$, то

То есть, наш массив записей стал разбит таким образом, что исходная задача сортировки сводится к двум независимым сортировкам пары массивов меньшей длины. Можно применять тот же метод к полученным подмассивам до тех пор, пока мы всё не отсортируем. При этом массивы единичной длины сортировать не надо.

Метод, рассмотренный нами, называется быстрая сортировка, а точнее общая быстрая сортировка.

Понятно, что эффективность алгоритма зависит от стратегии выбора записи $R$, по которой будем разделять массив. Эта запись называется опорным элементом разделения. Используя разные алгоритмы выбора опорного элемента мы будем получать разные варианты быстрой сортировки, такие как рандомизированная быстрая сортировка, быстрая сортировка Седгевика и быстрая сортировка Хоара. Операцию выбора этого элемента назовём select_pivot() и рассмотрим потом отдельно.

Также эффективность алгоритма зависит от способа разбиения подмассива на две части относительно опорного элемента. Как бы операция выбора опорного элемента является частью операции разбиения, но для удобства повествования и анализа я разделю эти две операции. Операция разделения partition(ref array[T] a, int left, int right, int pivot_index) -> int принимает на вход ссылку на исходный массив, границы подмассива для разделения и индекс элемента, который считается опорным. Возвращает индекс, на который переместился опорный элемент. При этом записи в подмассиве эта операция перекомпонует так, что по индексам от left до нового индекса опорного элемента располагаются только записи, у которых ключи меньше опорного, а по индексам от нового индекса опорного элемента до right располагаются только записи, у которых ключи больше опорного.

А пока общий код алгоритма быстрой сортировки

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

Если нам не повезет, и по нашей стратегии мы будем выбирать опорный элемент так, что одна часть будет состоять только из одной записи, а другая часть из всех оставшихся, то время работы нашего алгоритма составит $O(n^2)$. А если нам повезет, и массив разделится ровно пополам, то время работы нашего алгоритма составит $O(n \log n)$. Получается, что для получения хорошего алгоритма быстрой сортировки нам нужно удачно выбирать опорный элемент.

Для анализа различных стратегий выбора опорного элемента установим общие свойства, верные для любой реализации быстрой сортировки.

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

Пусть также $p_{n, \- k}$ — вероятность того, что опорный элемент разбивает исходный массив на подмассивы длины $k$ и $n-k-1$.

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

Пусть $G_n (x) = \sum\limits_{j=0}^\oo \prob(C = j) \cdot x^j$ — производящая функция вероятностей числа сравнений $C$ в быстрой сортировке массива из $n$ элементов.

Введём величину $a_{n, \- k}$ — число сравнений при разбиении при условии, что опорный элемент занимает позицию $k$. Пусть её производящая функция равна $A_{n, \- k} (x) = \sum\limits_{j=0}^\oo \prob(a_{n, \- k} = j) \cdot x^j$ Тогда

Это свойство производящей функции числа сравнений следует из сохранения случайности при разбиении.

Теперь получим формулы для $S$ — количество обменов. Это тоже случайная величина.

Пусть $H_n (x) = \sum\limits_{j=0}^\oo \prob(S = j) \cdot x^j$ — производящая функция вероятностей числа обменов $S$ в быстрой сортировке массива из $n$ элементов. Здесь опять $p_{n, \- k}$ — вероятность того, что опорный элемент разбивает исходный массив на подмассивы длины $k$ и $n-k-1$.

Введём также величину $b_{n, \- k}$ — число обменов при разбиении при условии, что опорный элемент занимает позицию $k$. Пусть её производящая функция равна $B_{n, \- k} (x) = \sum\limits_{j=0}^\oo \prob(b_{n, \- k} = j) \cdot x^j$ Тогда

Это свойство производящей функции числа обменов следует из сохранения случайности при разбиении и условной независимости числа обменов в подмассивах.

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

Данный алгоритм разбиения был предложен Нико Ломуто в 1970-х годах как простой вариант оригинального разбиения Хоара, а позже был популяризован в книгах Бентли (Programming Pearls) и Кормена (Введение в алгоритмы). В оригинале в качестве опорного выбирался строго последний элемент, для еще большего удобства реализации, но я все-таки буду придерживаться принципа максимальной общности и не буду закреплять выбор индекса, просто скажу, что индекс фиксирован.

Оценим количество сравнений, выполняемых быстрой сортировкой со схемой Ломуто.

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

Для фиксированного выбора опорного элемента $p_{n, \- k} = 1/n$ для всех $k$ от $0$ до $n-1$. Также при разбиении мы делаем фиксированное число сравнений — $n-1$, поэтому $A_{n, \- k} = x^{n-1}$ Подставляем в формулу $G_n (x)$:

Найти в замкнутом виде выражение для $G(x)$ не получится, но это нам и не нужно. Нам нужно просто посчитать, чему равны первая и вторая производная в точке $1$, чтобы посчитать математическое ожидание и дисперсию числа сравнений

Подставляем $x=1$, и, обозначив $E_n = G_n'(1)$, получаем рекуррентное соотношение для $E_n$:

Решая эту реккуренту получаем

Теперь обозначим $V_n = G_n''(1)$, и, посчитав вторую производную, получим рекуррентное соотношение для $V_n$:

Решая эту рекурренту получаем

Тогда

Максимальное число сравнений достигается тогда, когда опорный элемент оказывается самым минимальным. Для максимального числа сравнений $C_{\max\limits} (n)$ получаем рекурренту $C_{\max\limits}(n) = (n-1) + C_{\max\limits}(n-1)$ с $C_{\max\limits}(1) = 0$, решением которой является $C_{\max\limits} = n(n-1)/2$.

Минимальное число сравнений достигается тогда, когда опорный элемент постоянно является медианой, и обрабатываемый массив делится ровно пополам. Понятно, что совсем ровное деление мы получить на произвольном массиве не сможем, потому что размер массива может быть любой. Оценим пока тут немного грубовато. Для минимального числа сравнений $C_{\min\limits} (n)$ получаем рекурренту $C_{\min\limits}(n) = (n-1) + C_{\min\limits}\bigl( \lfloor (n-1)/2 \rfloor \bigr) + C_{\min\limits}\bigl( \lceil (n-1)/2 \rceil \bigr)$ с $C_{\min\limits}(0) = C_{\min\limits}(1) = 0$, грубым решением которой является $C_{\min\limits} < n \log_2 n - n + O(\log n)$.

Получаем все важные характеристики количества сравнений $C$:

Теперь оценим количество обменов.

Для фиксированного выбора опорного элемента $b_{n, \- k} = k$, и $B_{n, \- k} (x) = x^k$. Обратите внимание: я учитываю только обмены, которые происходят в цикле в операции разбиения и не учитываю служебные обмены, которые связаны с размещением опорного элемента, потому что количество служебных обменов зависит от реализации. Важно только то, что эти служебные обмены добавляют не более константы к числу обменов на каждом уровне разбиения, что приводит к линейной поправке в итоговой оценке количества обменов. Тогда наша рекуррента превращается в

И снова, найти в замкнутом виде выражение для $H(x)$ не получится. А нам и не надо. Нам надо только вычислить значения $E_n = H_n'(1)$ и $V_n = H_n''(1)$.

Начнём с первого момента, $E_n$. Считаем производную $H_n'(x)$, подставляем $x=1$ и получаем рекурренту

Решаем и получаем, что

Далее, считаем вторую производную $H_m''(x)$, подставляем $x=1$ и получаем рекурренту для $V_n$:

Решая эту рекурренту, получаем значение второго момента

Тогда

Максимальное число обменов достигается на полностью отсортированном массиве, где на каждом шаге опорный строго больше всех остальных элементов. Тогда $S_{\max\limits}(n) = n \, (n-1) / 2$.

Минимальное число обменов достигается на отсортированном массиве, ведь мы буквально никого ни с кем не обмениваем. Тогда $S_{\min\limits} = 0$.

Получаем все важные характеристики количества сравнений $C$:

Как мы поняли, метод неплохой, работает за ожидаемое время $O(n \log n)$, а точнее выполняет в среднем $2 n \ln n + O(n)$ сравнений и $n \ln n + O(n)$ обменов. У этого метода есть одна большая проблема: он уязвим к умышленным атакам. Алгоритм детерминированный, так что можно подобрать такой входной массив, что каждый раз будет в качестве опорного элемента выбираться наименьший или наибольший. И тогда нам гарантировано максимальное время работы $O(n^2)$.

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

Итак, давайте в качестве опорного элемента выбирать случайную запись. То есть опорным элементом $R$ может с равной вероятностью оказаться каждая из $n$ записей $R_1, R_2, \dotsc, R_n$.

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

При случайном выборе опорного элемента из всех $n$ позиций, вероятность того, что опорный элемент окажется на индексе $k$, и даст подмассивы размеров $k$ и $n-k-1$, равна $1/n$. Это точно такое же распределение $p_{n, \- k} = 1/n$, как и для фиксированного выбора опорного элемента на случайной перестановке.

Количество сравнений при разбиении $a_{n, \- k}$ тоже равно $n-1$.

Количество обменов при разбиении $b_{n, \- k}$ тоже равно $k$, ведь для случайной перестановки распределение числа обменов зависит только от позиции опорного элемента, а не от того, как он был выбран.

Получается, что производящие функции числа сравнений $C$ и числа обменов $S$ в обоих вариантах совпадают, а значит, я могу просто переписать результат анализа.

Для рандомизированной быстрой сортировки

В чём же тогда преимущество такого подхода? В том что этот вариант выбора опорного элемента недетерминированный, и к нему нельзя просто так подобрать плохие входные данные. Да, нам всё еще может не повести с выбором опорного элемента, но вероятность такого невезения крайне мала. А от умышленных атак этот алгоритм защищён, по крайней мере до того момента, пока злоумышленник не узнает алгоритм генерации случайных чисел и его сид. На практике это делает рандомизированную версию значительно устойчивее к враждебным данным

Рассмотрим оригинальный алгоритм разбиения, предложенный создателем быстрой сортировки Чарльзом Энтони Ричардом Хоаром в 1960 году.

Опорный элемент фиксированный, так что у нас опять $p_{n, \- k} = 1/n$.

Проанализируем число сравнений, которые случаются при быстрой сортировке со схемой разделения Хоара.

Каждый индекс посещается соответствующим указателем ровно один раз: указатель i начинает с левой границы и движется только вправо, а указатель j начинает с правой границы и движется только влево. Эти два указателя встречаются где-то посередине и останавливаются. Значит, каждый индекс будет посещён ровно одним из указателей, и для него произойдёт ровно одно сравнение ключа с опорным элементом.

Получается, что $A_{n,\-k} (x) = x^n$ для всех $k$. Подставляем в рекурренту для $G_n (x)$:

Считаем производную, подставляем $x=1$ и получаем рекурренту для $E_n = G'(1)$:

Решая эту реккуренту получаем

Теперь обозначим $V_n = G_n''(1)$, и, посчитав вторую производную, получим рекуррентное соотношение для $V_n$:

Решая эту рекурренту получаем

Тогда

Максимальное число сравнений достигается тогда, когда опорный элемент оказывается самым минимальным. Для максимального числа сравнений $C_{\max\limits} (n)$ получаем рекурренту $C_{\max\limits}(n) = (n-1) + C_{\max\limits}(n-1)$ с $C_{\max\limits}(1) = 0$, решением которой является $C_{\max\limits} = n(n-1)/2$.

Минимальное число сравнений достигается тогда, когда опорный элемент постоянно является медианой, и обрабатываемый массив делится ровно пополам. Понятно, что совсем ровное деление мы получить на произвольном массиве не сможем, потому что размер массива может быть любой. Оценим пока тут немного грубовато. Для минимального числа сравнений $C_{\min\limits} (n)$ получаем рекурренту $C_{\min\limits}(n) = (n-1) + C_{\min\limits}\bigl( \lfloor (n-1)/2 \rfloor \bigr) + C_{\min\limits}\bigl( \lceil (n-1)/2 \rceil \bigr)$ с $C_{\min\limits}(0) = C_{\min\limits}(1) = 0$, грубым решением которой является $C_{\min\limits} < n \log_2 n - n + O(\log n)$.

Получаем все важные характеристики количества сравнений $C$:

Проанализируем количество обменов, которое случается при быстрой сортировке со схемой разделения Хоара.

Опорный элемент не участвует в обменах до финального положения. Обмены происходят только между элементами левой и правой частями, при этом каждая пара $(i, j)$, где $i$ взят из левой части, а $j$ взят из правой части, может привести к обмену. Обменяются они тогда и только тогда, когда пара $(i, j)$ будет составлять инверсию. Получается, что число обменов при быстрой сортировке со схемой Хоара равно числу инверсий между левой и правой частями.

Массив разделён на две части, в одной $k$ элементов, а в другой $n-k-1$ элементов. Производящая функция для числа инверсий между множествами размера $k$ и $n-k-1$ равна гауссовому коэффициенту

Тогда, усредняя по всем равновероятным разбиениям, получаем производящую функцию $B_{n, \- k} (x)$ числа обменов операции разбиения по схеме Хоара

где $\inv (A, B)$ — число инверсий между множествами $A$ и $B$.

Теперь мы можем записать производящую функцию $H_n (x)$ и вычислить оба момента $S$, чтобы найти главные характеристики числа обменов.