Квадратичные алгоритмы сортировки

На практике сортировка «пузырьком» почти не используется. Причина проста: есть существенно более эффективные алгоритмы сортировки с той же асимптотической сложностью и примерно такой же сложностью реализации.

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

То есть устроены они так (в предположении, что переменная array связана с сортируемым массивом):

N = len(array)
for sorted_length in range(N):
  ## здесь происходят перестановки элементов, приводящие к 
  ## увеличению длины упорядоченного куска на 1

Сортировка поиском минимума

Для удлинения упорядоченной части на 1 мы ищем наименьший элемент неупорядоченной части и меняем его местами с начальным элементом неупорядоченной части:

N = len(array)
for sorted_length in range(N):
  _, min_index = min([(x, i + sorted_length) 
                      for i,x in enumerate(array[sorted_length:])])
  
  array[min_index], array[sorted_length] = (
    array[sorted_length], array[min_index]
  )

Асимптотическую сложность этого алгоритма нетрудно вычислить. Поиск минимального элемента (перебором) на каждом шагу алгоритма занимает не более \(N\) операций вида «посмотреть на элемент и что-нибудь запомнить», но и не менее \(N-sorted_length\) (в том случае, когда минимальный элемент — последний, на который мы посмотрели в процессе перебора).

Поэтому время работы алгоритма \(T(N)\) удовлетворяет неравенствам

\[ N\cdot N \geqslant T(n) \geqslant N + (N-1) + (N-2) + \ldots + 1 = \frac{N(N+1)}{2} \]

Осталось заметить, что \(N(N+1)/2 \geqslant \frac{1}{2} N^2\). Поэтому рассматриваемый нами алгоритм относится к классу квадратичных (т.е. асимптотической сложности \(N^2\)).

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

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

N = len(array)
for sorted_length in range(N):
  for k in range(sorted_length):
    i = sorted_length - k 
    if array[i] < array[i-1]:
      array[i], array[i-1] = array[i-1], array[i]
    else:
      break

Единственной сложностью реализации этого алгоритма является обеспечения корректности индекса i внутреннего цикла. Он должен быть в пределах от \(1\) (для того, чтобы было определено array[i-1]) до \(N-1\) (для того, чтобы было определено array[i]).

Поскольку k не превышает sorted_length-1, то sorted_length-k не меньше

sorted_length - (sorted_length - 1) = 1

Также, поскольку k не меньше нуля, а sorted_length не превышает \(N-1\), то sorted_length - k тоже не превышает \(N-1\).

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

Постскриптум

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

Может возникнуть естественный вопрос: «зачем вообще использовать квадратичный алгоритм сортировки, если есть алгоритмы с более низкой асимптотической сложностью?». Ответ весьма простой (хотя и состоит из двух частей):

• теория асимптотической сложности исследует лишь время работы алгоритма при достаточно большом \(N\)
• чем больше \(\alpha\), тем при большем количестве натуральных значений \(N\) выполнено неравенство \(\alpha N \log_2 N > N^2\)

Следствием любого из этих утверждений является то, что квадратичный алгоритм при достаточно маленьком \(N\) может работать быстрее линейно-логарифмического.

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