Быстрые алгоритмы сортировки

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

Сортировка слиянием

Заметим сперва, что два упорядоченных массива можно соединить в один (тоже упорядоченный) следующим образом:

def merge(a,b):
  result = []

  i,j = 0,0
  while i<len(a) and j<len(b):
    if a[i] < b[j]: result.append(a[i]); i+=1
    else:           result.append(b[j]); j+=1

  result.extend(a[i:])
  result.extend(b[j:])
    
  return result

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

def merge_sorted(a):
  if len(a) < 2: return a[:]
  
  m = len(a)//2
  return merge(merge_sorted(a[:m]), 
               merge_sorted(a[m:]))

Доказательство того, что этот алгоритм работает, причём достаточно «быстро», можно аккуратно провести в несколько этапов.

Корректность

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

Назовём этот самый короткий среди неупорядочиваемых массивов буквой A. Заметим следующее (каждый факт тривиальным образом следует из предыдущего):

  1. len(A) >= 2
  2. len(A)//2 >= 1 и len(A)//2 < len(A)
  3. len(A[:m]) < len(A) и len(A[m:]) < len(A), где m = len(A)//2
  4. merge_sorted(A[:m]) и merge_sorted(A[m:]) упорядочены
  5. merge_sorted(A) упорядочен

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

Асимптотическая сложность

Будем рассматривать только верхнюю асимптотическую сложность (нижняя равна \(N\log N\), поскольку рассматриваемый алгоритм удовлетворяет предположениям теоремы о нижней оценке асимптотической сложности алгоритма сортировки — траектория программы зависит только от результатов ветвлений).

Обозначим \(T(N)\) максимально возможное время работы программы на массиве длины \(N\). Теперь применим полезный «трюк». Введём обозначение \(T_m(N) = \mathop{\mathrm{max}}_{n\leqslant N} T(n) \).

Верно следующее:

  1. \(T(N) \leqslant T_m(N)\)
  2. последовательность \(T_m\) является неубывающей

Монотонность \(T_m\) нам очень пригодится в дальнейшем. А вот \(T\) нас вообще больше не будет интересовать: очень трудно оценивать сверху последовательность, которая иногда возрастает, а иногда убывает, но «в целом возрастает». В связи с этим далее под обозначением \(T\) мы будем всегда понимать \(T_m\).

Также доопределим \(T\) на весь луч неотрицательных чисел: будем считать \(T(x) = T(\lfloor x \rfloor)\). Тогда для любого \(x\geqslant 2\) верно следующее:

\[ T(x) \leqslant 2T(x/2) + \alpha x + \beta \]

Здесь \(\alpha\) определяется реализацией алгоритма слияния merge, а \(\beta\) — накладными расходами на арифметические операции и вызовы функций в определении merge_sorted.

Применим это неравенство \(k\) раз:

\[ T(x) \leqslant 2^k T(x/2^k) + \alpha kx + \beta (1 + 2 + \ldots + 2^{k-1}) \]

Возьмём \(k=\lfloor \log x \rfloor\). Тогда:

\[ T(x) \leqslant 2^k T(1) + (2^k-1)\beta + \alpha x \log x \]

Осталось заметить, что, начиная с достаточно большого \(x\), выполнено

\[ T(x) \leqslant 2\alpha x\log x \]

Это и требовалось доказать.

Сортировка разбиением

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

Сортировка разбиением разбивает массив на два куска так, чтобы слияние этих кусков было тривиальным:

def partition_sorted(a):
  if len(a) < 2: return a[:]

  left, pivot, right = partition(a)

  return partition_sorted(left) + [pivot] + partition_sorted(right)

Этого можно добиться, если любой элемент left не превосходит pivot, а любой элемент right не меньше pivot. Опорный элемент pivot отделён от обеих частей для того, чтобы их размеры были строго меньше len(a).

Простейшая реализация функции partition может выглядеть так:

def partition(a):
  pivot = a[0]
  left = []
  right = []

  for x in a[1:]:
    if x <= pivot: left.append(x)
    else:         right.append(x)

  return left, pivot, right

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

Асимптотическая сложность

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

Тем не менее, среднее время работы алгоритма оказывается (как мы далее покажем) линейно-логарифмическим. Поэтому обычно делают следующее:

  • выбирают опорный элемент более хитрым образом (например, псевдослучайно)
  • если алгоритм таки превысил некую глубину рекурсии, перезапускают его, или же переходят к другому алгоритму сортировку

Итак, сейчас мы будем оценивать не максимально возможное время работы, а среднее. Как и раньше, обозначим \(T\) результат монотонизации (теперь среднего) времени работы.

Теперь заметим, что для любого \(n\geqslant 2\) верно

\[ T(n) \leqslant \frac{T(0)+T(n-1) + T(1)+T(n-2) + \ldots + T(n-1)+T(0)}{n} + \alpha n + \beta \]

Если ввести обозначение \(S(n)=T(0)+T(1)+\ldots+T(n)\), то получим

\[ T(n) \leqslant \frac{2}{n} S(n-1) + \alpha n + \beta \]

Применив ещё раз такое неравенство, получаем

\[ T(n) \leqslant \frac{2}{n} \left( \left(1 + \frac{2}{n-1}\right)S(n-2) + \alpha\cdot(n-1) + \beta \right) + \alpha n + \beta \]

Что эквивалентно

\[ T(n) \leqslant \frac{2(n+1)}{n(n-1)} S(n-2) + \alpha \left( n + \frac{2(n-1)}{n} \right) + \beta \frac{n+2}{n} \]

Если ещё раз применить такое же неравенство (и тривиальную оценку для члена с \(\beta\)), получится:

\[ T(n) \leqslant \frac{2(n+1)}{(n-1)(n-2)} S(n-3) + \alpha\left( n + \frac{2(n-1)}{n} + \frac{2(n+1)(n-2)}{n(n-1)} \right) + \beta\frac{n+2+4}{n} \]

Сделав так ещё много раз, получим (желающие могут аккуратно вывести рекуррентные соотношения на коэффициенты формулы):

\[ T(n) \leqslant \frac{2(n+1)}{3\cdot 2} S(1) + \alpha \left( n + \sum_{k=1}^{n-2} \frac{2(n+1)(n-k)}{(n-k+1)(n-k+2)} \right) + \beta \frac{n + (n-2)(n-1)}{n} \]

Немного увеличив числа в правой части, получаем оценку:

\[ T(n) \leqslant n(S(1)+\alpha+\beta) + 4n\alpha \left( \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \ldots + \frac{1}{n} \right) \]

Осталось оценить сумму при \(4n\alpha\). Но это — уже совершенно стандартная задача (обычно изучающаяся на уроках математики в 7 или 8 классе).

Первым делом оценим эту сумму сверху суммой, в которой на два слагаемых больше:

\[ 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} \]

Дальше заметим, что:

  • первое слагаемое не превосходит единицу
  • следующие два слагаемых не превосходят половину; их сумма не превосходит 1
  • следующие четыре слагаемых не превосходят четверть; их сумма не превосходит 1
  • и т.д.

Поэтому, если слагаемых не больше \(1+2+\ldots+2^{m-1} = 2^m-1\), то вся сумма не превосходит \(m\). Отсюда сразу следует, что сумма не превосходит \(\lceil\log (n+2)\rceil\), что, начиная с \(n=2\), не больше \(2\log n\).

Итак, мы доказали, что

\[ T(n) \leqslant n(S(1)+\alpha+\beta) + 8n\alpha\log n \]

Но нам это и нужно было.

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

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

Разбиение происходит прямо в сортируемом массиве:

def partition_inplace(a, first, last):
  pivot = a[first]  ## можно заменить на что-нибудь более интересное

  while True:
    while a[first] < pivot: first += 1
    while a[last]  > pivot: last -= 1
    if first <= last:
      a[first], a[last] = a[last], a[first]
      first += 1; last -= 1
    if first > last:
      return last, first

Результат такого разбиения обладает следующими свойствами:

  • первая компонента результата меньше второй
  • первая компонента результата строго меньше входа last, а вторая — строго больше входа first
  • любой элемент отрезка [first,last] с номером, не большим первой компоненты результата, не больше опорного элемента
  • любой элемент этого отрезка с номером, не меньшим второй компоненты результата, не меньше опорного элемента

В терминах такого разбиения алгоритм быстрой сортировки выражается так:

def quicksort_rec(a, first, last):
  if last - first <= 0: return
  l, r = partition_inplace(a, first, last)
  quicksort_rec(a, first, l)
  quicksort_rec(a, r, last)

def quicksort(a): quicksort_rec(a, 0, len(a)-1)

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

Существенно проще для реализации похожие схемы, в которых один из обмениваемых элементов — опорный. Впрочем, они менее эффективны.