Сортировка

Определение

Функция сортировки массива - любая функция с сигнатурой $[f\colon\ 'a\ array \to\ 'a\ array]$, такая что:

$\begin{cases} \left [ \begin{matrix} \forall x, y \in \overline {0, (n-1)}\ x < y \Rightarrow {(f(a))}_x \leq {(f(a))}_y \\ \forall x, y \in \overline {0, (n-1)}\ x < y \Rightarrow {(f(a))}_x \geq {(f(a))}_y \end{matrix} \right . \\ \forall x \in \overline {0, (n-1)}\ \exists y \in \overline {0, (n-1)}\ a_x = (f(a))_y \end{cases}$

Таким образом, сортировкой массива называется применение функции сортировки массива к массиву.

Классификация

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

О-нотация

Определение

Пусть $f(x)$ и $g(x)$ — две функции, определенные на некоторой проколотой окрестности точки $x_0$, причем в этой окрестности $g(x) \ne 0$; кроме того, пусть определена функция $Nb'(x)$ взятия выколотой окрестности точки. Тогда:

$<br />{\mathcal O}(g(x)) = \{f(x) \mid<br />\exists C \in {\mathbb R^+}\ \forall x \in Nb'(x_0)\ |f(x)| \underset {x \rightarrow x_0} \leq C|g(x)| \}<br />$

Часто вместо знака принадлежности используют знак равенства, поэтому данное выше определение можно переписать так:

$<br />f(x) \underset {x \rightarrow x_0} = {\mathcal O}(g(x)) \iff<br />\exists C \in {\mathbb R^+}\ \forall x \in Nb'(x_0)\ |f(x)| \leq C|g(x)|<br />$

Иными словами, $f(x) = {\mathcal O}(g(x))$, если отношение $\left | \frac {f(x)} {g(x)} \right |$ ограничено сверху некоторой константой $C$.

Следствия

$O(f(x)) = O(Cf(x))$ - очевидно вытекает из определения

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

Пусть определено сравнение элементов в массиве, а также функция $[swap\colon\ 'a\ array \to\ int \to int]$, меняющая местами два элемента.

 let swap a i j =
  let t = a.(i) in
  a.(i) <- a.(j);
  a.(j) <- t

Сортировка пузырьком

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

 let bubble a =
  let changed = ref false in
  let rec step () =
   for i = 0 to Array.length a - 2 do
    if a.(i) > a.(succ i) then (swap a i (succ i); changed := true)
   done; if !changed then (changed := false; step ()) in step ()

Сложность алгоритма - $O(n^2)$, расход памяти - $O(1)$.

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

Также известна как qsort. Один из самых быстрых алгоритмов, который к тому же прост в реализации. Основная идея такова: поделить массив пополам, отсортировать обе части относительно середины (то есть слева всё меньше середины, справа всё больше/равно), продолжить рекурсивно. Реализация для списков очевидна.

 let qsort = function
  |[] -> []
  |[x1] -> [x1]
  |x1::xs -> qsort (List.filter (fun x -> x <  x1) xs) @ [x1] @
             qsort (List.filter (fun x -> x >= x1) xs)

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

 let qsort a =
  let rec qsort l r =
   if l >= r then () else (
   let pl = ref l (* левый указатель *)
   and pr = ref r (* правый указатель *)
   and m = a.((l + r) / 2) in (* значение середины *)
   while (!pl <= !pr) do
    while (a.(!pl) < m && (!pl <= r)) do incr pl done; (* сдвигаем указатели настолько, *)
    while (a.(!pr) > m && (!pr >= l)) do decr pr done; (* насколько возможно *)
    if !pl <= !pr then (if !pl < !pr then swap a !pl !pr; incr pl; decr pr;);
     (* а когда указатели упрутся в неправильно стоящие элементы, они меняются местами *)
   done;
    (* в конце концов указатели где-то столкнутся, *)
    (* после чего нужно рекурсивно отсортировать обе половины *)
   if !pl < r then qsort !pl r;
   if l < !pr then qsort l !pr) in
  qsort 0 (pred (Array.length a))

Сложность алгоритма - $O(n \log n)$ в среднем, $O(n^2)$ в худшем случае, расход памяти - $O(1)$.

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

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

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

Сложность алгоритма - $O(n \log n)$, расход памяти - $O(n)$.

Сортировка кучей

Самый нетривиальный алгоритм из описанных здесь. Идея такая: сначала массив превращается в двоичное дерево, иными словами, в такую структуру, где у каждого элемента может быть до двух потомков. Самое интересное, что эту операцию можно проделать in-place (тем самым экономя кучу времени), если считать, что потомками элемента a.(n) являются элементы a.(2n + 1) и a.(2n + 2). После этого из дерева восстанавливается отсортированный массив. Сделать это не очень трудно. Заметим, что в куче всегда дедушка - самый большой. Тогда, если запихать его в конец, он окажется в правильном положении. После чего будем игнорировать конец массива с дедушками и восстановим слева от них дерево. Повторять, пока дедушки не кончатся.

 (* функция, работающая при создании двоичного дерева;
    вызывается один раз для каждого элемента при проходе
    через массив слева направо; считается, что всё, что
    находится слева от указателя, переданного функции -
    уже построенное дерево *)
 let lift a n =
  let rec lift pos =
   if pos = 0 then () else (* дедушку не трогать! *)
   let dad = if pos mod 2 = 0 then pred (pos / 2) else (pos / 2) in
    (* нахождение из 2n + 1 либо 2n + 2 -> n *)
   if a.(pos) > a.(dad) then
    (* если надо, меняем местами отца и сына и продолжаем издевательство
       следует отметить, что вызов [lift dad] на самом деле никакого отношения
       к папе не имеет, так как перед ним находится swap *)
    ( swap a pos dad; lift dad ) in
  lift n;;
 
 (* эта функция работает при восстановлении отсортированного массива;
    она получает указатель на текущую правую границу массива, точнее,
    на последний элемент, приадлежащий дереву (правее - только дедушки,
    а они уже отсортированы *)
 let sink a n =
  let rec sink pos =
   if pos >= n then () else
   (* нахождение потомков: c1 = 2n + 1, c2 = 2n + 2 *)
   let c1 = succ (pos * 2) in
   let c2 = succ c1 in
   if c1 > n then () else (* если даже 2n + 1 вышел за границу массива, говорить не о чём *)
    (* а вот в этом случае можно немного повозиться *)
   if c2 > n then (if a.(c1) > a.(pos) then ( swap a c1 pos; )) else
    (* упорядочиваем детей по убыванию *)
   let (c1, c2) = (if a.(c1) >= a.(c2) then (c1, c2) else (c2, c1)) in
    (* и восстанавливаем дерево *)
   if a.(c1) > a.(pos) then ( swap a c1 pos; sink c1 ) else
   if a.(c2) > a.(pos) then ( swap a c2 pos; sink c2 ) in
  sink 0
  
 let heap a =
  let last = pred (Array.length a) in
   (* строим дерево *)
  for i = 0 to last do
   lift a i;
  done;
   (* восстанавливаем массив *)
  for i = last downto 1 do
   swap a 0 i;
   sink a (pred i);
  done

Сложность алгоритма - $O(n \log n)$, расход памяти - $O(1)$.

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

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

 let insertion a =
  for i = 1 to Array.length a - 1 do
   let j = ref (i - 1) in
   while (!j >= 0) && (a.(!j) > (a.(!j + 1))) do
    swap a (!j) (!j + 1);
    decr j;
   done;
  done

Сложность алгоритма - $O(n^2)$, расход памяти - $O(1)$.

Сортировка Шелла

Сильно улучшенный вариант сортировки вставками. Отличается тем, что работает в несколько проходов, причём сначала сравниваются и сортируются элементы, отстоящие друг от друга на некоторое расстояние, которое с каждым проходом уменьшается. Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов.

 let steps = [|1750; 701; 301; 132; 57; 23; 10; 4; 1|]
 
 let insertion a d off =
  for i = 1 to (Array.length a - off) / d - 1 do
   let j = ref (i * d + off) in
   while (!j - d >= 0) && (a.(!j - d) > (a.(!j))) do
    swap a (!j - d) (!j);
    j := !j - d;
   done;
  done
 
 let shell a =
  let len = Array.length a in
  let stptr = ref 0 in
  while (steps.(!stptr) > len) do incr stptr done;
  while (!stptr < Array.length steps) do
   for off = 0 to steps.(!stptr) - 1 do
    insertion a (steps.(!stptr)) off
   done;
  incr stptr;
  done

Сложность алгоритма зависит от выбранного набора шагов и входных данных, расход памяти - $O(1)$.

Сортировка подсчётом

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

 let countsort a =
  let counter = Array.create 10 0 in
  let incr_counter i = counter.(i) <- succ counter.(i) in
  for i = 0 to pred (Array.length a) do
   incr_counter a.(i);
  done;
  let ptr = ref 0 in
  for i = 0 to 9 do
   for j = 1 to counter.(i) do
    a.(!ptr) <- i;
    incr ptr;
   done;
  done

Сложность алгоритма - $O(n)$, расход памяти зависит от входных данных и может возрастать до $O(n)$.

Поразрядная сортировка

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

Код приводить не буду - во-первых, он очевиден, во-вторых, лень.

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

S(n)

S(n) - это функция, вычисляющая наибольшее количество сравнений, необходимое для работы наилучшего алгоритма сортировки. Для того чтобы понять, как она работает, для начала введём несколько определений. Сначала заметим, что в процессе работы любой алгоритм сортировки обязан выполнить некоторое количество сравнений. Эти сравнения можно изобразить в виде графа, вершины которого - это элементы массива, а стрелки, их соединяющие, изображают уже совершённые сравнения на данном этапе. Пусть если из элемента A есть стрелка в элемент B, то A < B. Обозначим граф сравнений на некотором этапе работы алгоритма за G и определим функцию T(G), возвращающую количество возможных способов упорядочить массив, располагая только сравнениями, известными на текущий момент (даа, не так-то легко её написать...). Заметим, что цель любого алгоритма сортировки - сделать достаточно сравнений, чтобы T(G) равнялась единице. Также определим функцию E(G, k) (эффективность графа сравнений):

$E(G, k) = E_k(G) = \frac {n!} {2^k T(G)}$ (n - кол-во элементов, которые мы сортируем)

Теперь рассмотрим такую ситуацию: произведено ещё одно сравнение и нам хочется узнать, как изменилась эффективность графа. Понятно, что результат сравнения двух элементов может быть двояким: либо $A \leq B$, либо $A > B$. Обозначим один из получившихся графов за $G_1$, а другой за $G_2$, здесь порядок не важен, и далее будет объяснено, почему. А теперь начинается интересное. Заметим, что $T(G) = T(G_1) + T(G_2)$. Сейчас советую сделать паузу и осознать сказанное :)

Пусть $T(G_1) \leq T(G_2)$. Обозначения выбирались случайно, поэтому можно в любой момент их поменять. Теперь отметим следующий факт:

$T(G) = T(G_1) + T(G_2) \leq 2T(G_2) \Rightarrow$

$T(G) \leq 2T(G_2) \Rightarrow$

$\frac {1} {T(G)} \geq \frac {1} {2T(G_2)} \Rightarrow$

$\frac {n!} {T(G)} \geq \frac {n!} {2T(G_2)} \Rightarrow$

$\frac {n!} {2^k T(G)} \geq \frac {n!} {2^{k+1}T(G_2)} \Rightarrow$

$E_k(G) \geq E_{k+1}(G_2)$

То есть на каждой итерации алгоритма сортировки эффективность графа сравнений не увеличивается.

Далее, заметим, что результатом работы любого алгоритма сортировки является такой граф:

$G^*: a_1 \rightarrow \dots \rightarrow a_n$

Также введём следующее обозначение:

$e = E_{\lceil\log_2 n! \rceil} (G^*) = \frac {n!} {2^{\lceil\log_2 n! \rceil}} \leq 1$

Далее идут комментарии Толи:

Вместо функции S(n) опишем функцию, проверяющую возможность сортировки за данное число операций.

Проверять будем перебором с небольшой оптимизацией: на каждом шаге получаем список графов, по каждому из этих графов выдаем список графов, полученных добавлением к исходному графу еще одного возможного сравнения и объединяем эти списки. Оптимизация:

1. Если эффективность получившегося графа < e, то граф выкидываем.
2. Выкидываем одинаковые графы.
3. Введем эквивалентность элементов: x ~ y, если множество элементов, больших x, совпадает с множеством элементов, больших y, и множество элементов, меньших x, совпадает с множеством элементов, меньших y; сравнение x1 и y1 ~ сравнению x2 и y2, если (x1 ~ x2) && (y1 ~ y2).

Добавляя сравнение к графу, если сравнение, эквивалентное данному уже добавлялось, то данное сравнение не добавляется.

Таким образом S(n) есть рекурсивный вызов этой функции от 1 до тех пор, пока она не выдаст true.

P.S.: набивать самостоятельно текст уже задолбало, поэтому привожу фрагмент письма от Штукенберга:

Идея такая: нам надо доказать, что наилучший алгоритм сортировки имеет худшее время S(n). Для этого надо показать, что:

1. Есть алгоритм, реализующий S(n)
2. Нет алгоритма, работающего S(n)-1 или быстрее.

E(G,k) и т.п. - это относится к пункту 2. Пункт 1 доказывается независимо. Для n <= 11 есть алгоритм, реализующий идеальное время - [log2 n!], поэтому эти случаи неинтересны. Для n = 12 есть алгоритм, требующий 30 шагов (подробно не рассматривался, требовать не буду), а [log2 n!] = 29. Отсюда вопрос - есть ли алгоритм, имеющий худшее число сравнений 29?

Задача п. 2 - найти по контрпримеру для любого алгоритма, т.е., каков бы ни был алгоритм сравнений, он найдет нужный случай, где нельзя будет ответить за 29 шагов. (алгоритм сравнений - это не программа, это большое дерево, где каждому результату сравнения сопоставлены два варианта продолжения сравнений - в зависимости от результата; мы его рисовали, когда доказывали оценку [log2 n!]).

Ага, только меня тогда не было :(

Отсортированный массив соответствует линейному графу. Если в нем есть разветвления и т.п. - это значит, что про какие-то два элемента их взаимное расположение нам неизвестно, и его требуется дополнительно выяснить. Поэтому, если на 29-м шаге сравнений граф сравнений не линеен - это значит, что конкретный алгоритм не годится.

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

Этим мы и занимаемся. Полный перебор (мы же перебираем дерево алгоритмов! - это очень большая структура) загнётся сразу, поэтому мы используем оптимизацию с E(G,k) и также дополнительно делаем несколько смелых предположений - что если при сравнении получаются два графа разной эффективности - надо брать граф с наименьшей (в нем, нам так кажется, с большей вероятностью найдется контрпример); мы имеем право это делать, потому что в реальном сравнении сравнение даст какой-то конкретный результат. А раз мы строим контрпримеры - значит, мы имеем право выбирать результаты сравнений. Расчет и правда оправдался, соответствующая программа была написана Марком Уэлсом в 1965 году - и подтвердила, что S(12) > 29.