\Section{Сортировки}{2 октября}{Валерий Черепанов}

\Subsection{Сортировки за $n\log n$}

\Subsubsection{Сравнение}

\begin{tabular}{l c c c c}
    & Fast & Stable & Inplace & Deterministic \\
    Quick & + & - & + & - \\
    Merge & - & + & - & + \\
    Heap  & - & - & + & + \\
\end{tabular}

Для каждой сортировки существует стабильный вариант ценой дополнительной памяти. Например, можно сортировать не сами элементы, а пары \{элемент, индекс\}.

\Subsection{Сортировки, бывающие быстрее $n \log n$}

\Subsubsection{Модифицированный HeapSort}

Работает за $\O(n\log n)$, но бывает быстрее.

Сначала построим кучу $H$ за $\O(n)$, а еще создадим кучу кандитов $C$ (изначально содержит только минимальный элемент кучи $H$). Теперь на каждом шагу будем вытаскивать минимальный элемент из кучи $C$, вставлять на следующую позицию в отсортированом массиве и добавлять в кучу $C$ детей текущего элемета из $H$.

Размер кучи $C$ в худшем случае может быть $(n+1)/2$, но в лучшем (когда минимальные элементы в куче $H$ лежат в порядке обхода DFS-а) он не превышает $\log n$. Следовательно, на некоторых входах можно добиться времени работы порядка $\O(n\log\log n)$.

\Subsubsection{Adaptive HeapSort}

Алгоритм создан в 1992 году.

Сначала строем кучу, испoльзуя декартово дерево по неявному ключу (то есть представим каждую вершину в виде точки на плоскости, где $x$ "--- значение в вершине, а $y$ "--- индекс элемента). Существует алгоритм со стеком, который делает это за $\O(n)$. Теперь используем модифицированный HeapSort из прошлого пункта.

В некоторых случаях будет работать за $\O(n)$.
\begin{enumerate}
    \item Когда вход уже отсортирован (причем в любую сторону).
    \item Конкатенация $k$ отсортированных массивов ($\O(n\log k)$) (на лекции было простое доказательство для $k=2$).
    \item Когда мало инверсий, ведь алгоритм работает за $\O(n\log \frac{\text{Inv}}n)$, где Inv "--- количество инверсий.
\end{enumerate}

\Subsection{Integer Sorting}

Числа можно сортировать быстрее, потому что у них есть быстрая операция индексации и быстрая операция деления, которое монотонно (то есть если $a \leq b$, то $a/x \leq b/x$ для всех $x > 0$).

Замечание: все сортировки в этом разделе работают для чисел, помещающихся в машинное слово (размера $2^b$, в современных компьютерах, как правило $b = 64$) и предполагают, что деление работает за $\O(1)$ (хотя на практике это не так).

\Subsubsection{CountSort}

Стабильна, работает за $\O(n+m)$, где $m$ такое, что $\forall i~0 \leq a_i \le m$.

\begin{code}
count = [0] * m
for e in a:
    count[e]++
for x in [0, m):
    pos[x+1] = pos[x] + count[x]
for i in [0, n):
    b[pos[a[i]]++] = a[i]
\end{code}

\Subsubsection{Digital (Radix) Sort}

Сортируем бинарные строки длины $m$ (числа от $0$ до $2^m-1 = M$).

Сначала [стабильно] сортируем по последнему элементу, потом по предпоследнему и т.д. Корректность легко доказать по индукции.

Время работы алгоритма $\O(nm)=\O(n\log M)$, где $M$ "--- максимальное число.

Можно выполнять эту сортировку не только в двоичной системе, но и в любой другой. Тогда время работы будет $\O((n+k)\log_k M)$.

\begin{Thm}
    Выгоднее всего брать $k=n$.
\end{Thm}

\begin{proof}

    Случай 1: $k \geq n$ тогда $n+k=\O(k)$ $k\log_k M = \frac k {\log k} M$ \\
    Случай 2: $k \leq n$ Тогда $n+k=\O(n)$ $n\log_k M = n \frac{\log M}{\log K}$
\end{proof}

\Subsubsection{BucketSort}

Сортировка называется BucketSort, так как она раскладывает числа по ведрам (bucket "--- ведро). Она хороша тем, что работает за линию на любых случайных перестановках.

\begin{enumerate}
    \item Найдем min и max за $\O(n)$.
    \item Если min = max, все числа равны, поэтому отсортированы, выйдём.
    \item Каждое $x_i$ кладем в bucket (ведро) номер $\lceil \frac{x_i-\text{min}}{\text{max}-\text{min}+1}\cdot n\rceil$.
    \item Теперь каждое ведро нужно отсортировать. Тут есть 2 варианта "--- рекурсивно вызвать BucketSort (BB)
      или использовать InsertionSort (BI). BI может быть выгоден, так как ведра маленькие.
\end{enumerate}

\pagebreak
\begin{Thm} $BB \leq n \log_2 M$ \end{Thm}
\begin{proof} Это верно, так как на каждом уровне рекурсии числа разбиваются минимум на 2 ведра, и на каждом уровне рекурсии чисел всего $n$.\end{proof}

\begin{Thm} $M \leq n \Rightarrow BB = \Theta(n) \text{ и } BI=\Theta(n)$ \end{Thm}
\begin{proof}

Получается что-то очень похожее на CountSort и с таким же временем работы. \end{proof}

\begin{Thm} На случайном входе и $M > n$ алгоритм работает за $\O(n)$ \end{Thm}
\begin{proof} Время работы алгоритм $\sum{k_i^2}$, где $k_i$ -- размер $i$-го ведра.
Если все числа случайные величины, порождённые равномерным распределением, то средняя величина $\sum{k_i^2}$ равна $\O(n)$.
Доказательство последнего смотрите в лекции 16.
\end{proof}
