Постановка задачи Резюмируем: Сортировка слиянием Основная идея: Резюмируем Быстрая сортировка Основная идея: Рандомизированный алгоритм Резюмируем Детерминированная быстрая сортировка Детерменированный алгоритм поиска k-й порядковой статистики за $O(n)$ Резюмируем Сортировка чисел Сортировка подсчётом(Counting sort) Стабильные сортировки Стабильная сортировка подсчётом Цифровая сортировка(Radix sort) Основная идея: Резюмируем

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

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

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

То есть изучение данного класса алгоритмов необходимо по той причине, что не существует "серебряной пули", хорошо справляющейся с любой задачей.

Постановка задачи

Пусть есть $n$ элементов $a_1,..,a_n$ с заданным отношением линейного порядка.

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

Задача заключается в поиске перестановки, такой, что $a_{\pi(1)}..a_{\pi(n)}$, где $\forall i < j : a_{\pi(i)} < a_{\pi(j)}$.
Сама $\pi$ перестановка является биекцией: ${1..n} \rightarrow {\pi(1)..\pi(n)}$

Теорема: Пусть, единственное, что можно делать с объектами - сравнивать их. Тогда для сортировки потребуется $O(n\ log\ n)$.

Док-во: Напомним, что задачей сортировки является поиск перестановки, в которой все объекты будут расположены в неубывающем порядке. То есть для любых двух объектов $a$ и $b$ будет верно одно из высказываний: $a \leq b$ или $a > b$. Такжы мы знаем что:

1. Искомая перестановка в худшем случае единственна.
2. В начале поиска у нас есть $n!$ перестановок.

   Зафикисруем первый элемент можем для этого взять один из $n$ элементов, Тогда на второе место можно поставить $n-1$ оставшийся элемент. Продолжая эту цепочку получим $$\prod_{i=n}^1i=n!$$

За одну операцию мы можем сравнить только 2 числа. А значит кол-во возможных перестановок после первого шага будет $\geq \frac{n!}{2}$, а после $i$-го Соответсвенно получим:

0	1	2	3	..	k
$n!$	$\frac{n!}{2}$	$\frac{n!}{4}$	$\frac{n!}{8}$	..	1

Что равно $log_2 \ n!$

Докажем, что полученное выражение равно: $$log_2\ n! = \Omega(n\ log\ n)$$ Лемма: $log \ n! = \Theta(n\ log\ n)$

Док-во:

$$log\ n! = log\ 1 * 2 * .. * n = \sum_{i=1}^{n} log \ i = O(n\ log\ n)$$

$$log\ n! = \sum_{i=1}^{n}log\ i \geq \frac{n}{2} log \frac{n}{2} = \Omega(n\ log\ n)$$

Резюмируем:

На данном этапе получили очень важный результат. Если немного переформулировать, то можно сказать, что без использования специальных структур и знаний о сортируемых данных, максимум на что мы можем расчитывать - это $\Omega(n\ log\ n)$.

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

Теперь постараемся найти алгоритм, который работает за такое время.

Основная идея:

1. Если длина массива больше одного, то рекурсивно выполним процедуру split, которая разделит массив пополам.
2. Выполним процедуру merge, которая "сливает" 2 уже отсортированных массива в 1

Пусть дан массив [1,3,4,2] По п.1: [1,3] [4,2] По п.1 для левой и правой части сразу [1] [3] [4] [2] По п.2 для левой и правой части сразу [1,3] [2,4] По п.2 [1,2,3,4]

Код процедуры merge и split:

Haskell:
merge :: Ord a => [a] -> [a] -> [a]
merge [] x  = x
merge  x [] = x
merge l@(lx:ls) r@(rx:rs) = if lx <= rx then lx : merge ls r else rx : merge l rs   

split :: [a] -> ([a], [a])
split l = splitAt (((length l) + 1) `div` 2) l

Python:
import math

def merge(arr_l, arr_r):
    results = []
    left_i = 0
    right_i = 0

    len_l = len(arr_l)
    len_r = len(arr_r)
    
    while (left_i < len_l) and (right_i < len_r):
        val_l = arr_l[left_i]
        val_r = arr_r[right_i]
        if val_l <= val_r:
            results.append(val_l)
            left_i += 1
        else:
            results.append(val_r)
            right_i += 1
    else:
        if len_l == left_i:
            results.extend(arr_r[right_i:])
        else:
            results.extend(arr_l[left_i:])
    return results

Python:
def split(arr):
    sep_id = math.ceil(len(arr)/2)
    return (arr[:sep_id], arr[sep_id:]) 

Код сортировки:

Haskell:
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [e] = [e]
mergeSort e = foldr merge [] $ (\(x,y) -> pure mergeSort <*> [x, y]) $ split e

Python:
def merge_sort(arr):
    arr_l = len(arr)
    if arr_l < 2:
        return arr
    else:
        (lh, rh) = split(arr)
        (lr, rr)= (merge_sort(lh), merge_sort(rh))
        return merge(lr,rr)

Посчитаем сложность этой сортировки при помощи Мастер-теоремы из прошлой задачи: $$T(n) = 2\ T\frac{n}{2} + O(n)$$ что равно $O(n\ log\ n)$

Резюмируем

У нас получилось найти сортировку за $O(n \ log \ n)$. Но рассмотрим один случай. Пусть у нас есть массив [1,2,3,4,5,6,8,7] Его сортировка будет занимать почти столько же времени, сколько и сортировка массива [8,7,6,5,4,3,2,1], хотя оптимально только поменять числа 7 и 8 местами.

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

Рассмотрим другую, очень популярную сортировку. И доберёмся до алгоритма, который позволит нам работать за $O(n\ log\ n)$ в среднем.

Основная идея:

1. Выберем из массива один элемент при помощи процедуры pivot.
2. При помощи процедуры partition разделим массив на 2 части: $\geq$ pivot-элемента и соответственно <.
3. На каждой из частей запустим шаг 1 рекурсивно.
4. Объединим полученные подмассивы.

Пусть дан массив [3,1,4,2]
Будем в качестве partition всегда брать первый элемент По п.1 3 [1,4,2] По п.2 [1,2] 3 [4] По п.3 для левого подмассива 1 [2] 3 [4] По п.4 [1,2] 3 [4] По п.4 [1,2,3,4]

Код процедур pivot и partition:

Haskell:
pivot :: [a] -> (a, [a])
pivot (x:xs) = (x, xs)

partition :: Ord a => a -> [a] -> ([a], [a])
partition p [] = ([],[])
partition p (x:xs) = if p >= x then (\(l,r) -> (x:l,r)) $ partition p xs else (x:) <$> partition p xs  

Python:
def pivot(arr):
    return (arr[0], arr[1:])

def partition(p, arr):
    lh = []
    rh = []
    for e in arr:
        if p >= e:
            lh.append(e)
        else:
            rh.append(e)
    return (lh,rh)

Код сортировки:

Haskell:
qSort :: Ord a => [a] -> [a]
qSort [] = []
qSort [x] = [x]
qSort x = let
  p = pivot x
  in (\(x:y:_) -> x ++ [fst p] ++ y) $ (\(l,r) -> qSort <$> [l,r]) $ uncurry partition $ p

Python:
def q_sort(arr):
    if len(arr) < 2:
        return arr
    (p, t) = pivot(arr)
    (lh,rh) = partition(p,t)
    lhr = q_sort(lh)
    rhr = q_sort(rh)
    return lhr + [p] + rhr

---

У нашего алгоритма в текущем виде есть один серьёзный недостаток. Он слишком зависим от входных данных. Т.е. возьмём массив [4,3,2,1]. При таком входе процедурой partition будет отсекаться только один элемент и время работы алгоритма вырастает до $O(n^2)$ .

Рандомизированный алгоритм

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

Теорема: Математическое ожидание работы алгоритма есть $O(n\ log n)$

Док-во: Время работы алгоритма пропорционально кол-ву сравнений. Обозначим через $D$ массив $A$ после сортировки.

Если входной массив A=[4,2,1,3], то D=[1,2,3,4]

Найдём, с какой вероятностью $D_i$ и $D_j$ будут сравниваться в алгоритме при ($i < j$).

Сравнения происходят только между pivot($x$) и одним из чисел. Т.е. числа в дальнейшем могут сравниваться только если $x \leq D_i \leq D_j$ или $D_i \leq D_j \leq x$. При этом очевидно, что если pivot лежит между этими числами, то они точно не смогут сравниться. А значит вероятность выбора pivot при котором $D_i$ и $D_j$ не сравнятся ,будет равна $\frac{2}{j - i + 1}$

Обозначим через $k$ - знаменатель, и заменим сумму с индексами на сумму расстояний между $D_i$ и $D_j$ Получим матожидание $$E T(n) \sim \sum_{i<j}\frac{2}{j-i+1} = \sum_{k=2}^{n}\frac{2}{k}\ (n-k+1) \leq \sum_{k=2}^{n} \frac{2}{k}\ n$$ Докажем, что полученное выражение равно $O(n \ log \ n)$

---

Лемма: $$S_n = \frac{1}{1} + \frac{1}{2} + .. + \frac{1}{n} = \Theta(log\ n)$$ Док-во: Пусть $2^k$ - максимальная степень двойки, т.ч. $2^k \leq n$ ($k \leq log_2 \ n$) . $S_n \geq S_{2^k} \geq \frac{1}{2} \ log_2\ 2^k \geq \frac{k}{2} = \Omega(log_2\ n)$

Пусть $2^m$ - минимальная степень двойки, т.ч. $2^m \geq n$ ($m \geq log_2 \ n$) . $S_n \leq S_{2^m} \leq 1\ log_2\ 2^m \leq m = O(log_2 \ n)$

---

Резюмируем

У нас получилос найти рандомизированный алгоритм, который работает за $O(n\ log\ n)$. Но что если мы хотим получить эффективный алгоритм, который работает за $O(n\ log\ n)$ всегда?

Детерминированная быстрая сортировка

Какой partition для нас является идеальным? Очевидно, что если partition разбивает массив на 2 равных подмассива, а не отсекает всего несколько элементов. Введём понятие медианы массива.

Определение: Элемент с индексом $\lfloor\frac{n+1}{2} \rfloor$ после сортировки называется медианой массива.

Поиск k-й порядковой статистики

Задача: по массиву $a_1,..,a_n$ найти $k$-ую порядковую статистику за $O(n)$ в среднем.

Теорема: Если среднее время работы $T(n)$ алгоритма поиска порядковой статистики, то $T(n)=O(n)$

Д-во: Пусть на массиве $A$, где $|A| = 1$, $T(1) = 1$. Пусть partition работает за $c|A|$

$$T(n) \leq \frac{1}{n}\sum_{i=1}^{n-1} max{T(i),T(n-i)} + cn$$ Докажем по индукции, что $\exists a: T(n) \leq an$: База: $T(1) \leq a;1 \Rightarrow a \geq 1$
Переход: Пусть $$\forall j \in {1..n-1}: T(j) \leq aj$$ $$T(n) \leq \frac{1}{n} \sum_{i=1}^{n-1}max{T(i), T(n-i)} + cn =$$ $$\frac{1}{n}\sum_{i=1}^{n-1}T(max{i,n-i}) + cn \leq$$ Теперь сделаем суммирование по значениям максимума. Каждый из максимумов может встретиться нам 2 раза(Пары $m,n-m$ и $n-m,m$) $$\frac{2}{n} \sum_{m=\frac{n}{2}}^{n-1}T(m) + cn \leq$$ И наконец, применим предположение индукции для всех $m$: $$\frac{2}{n} \sum_{m=\frac{n}{2}}^{n-1} am + cn =$$ Вспомним, что ряд $1+..+s =\frac{s(s+1)}{2}$:

$$\frac{2a}{n}(\sum_{m=1}^{n-1}m - \sum_{m=1}^{\frac{n}{2} - 1}m) + cn = \frac{2a}{n}(\frac{(n-1)n}{2} - \frac{(\frac{n}{2} - 1)\frac{n}{2}}{2}) + cn = a(n-1 -\frac{n}{4} + \frac{1}{2}) + cn$$

$$= a(\frac{3n}{4} - \frac{1}{2}) + cn = n(\frac{3a}{4} + c) - \frac{a}{2} \leq n(\frac{3a}{4} + c)$$

Что завершает доказательство.

Детерменированный алгоритм поиска k-й порядковой статистики за $O(n)$

Разобъём массив $a_1,..,a_n$ на блоки по 5 элементов. В каждом блоке найдём медиану за $O(1)$

Можно выбрать другой размер блока, но больше 3.

Получим $\frac{n}{5}$ медиан Запустимся рекурсивно на полученном массиве. Получим некую медиану $x$

Алгоритм:

1. Находим медиану
2. Делаем partition
3. Если наша порядковая статистика больше левого разбиения, то запускаемся на правом, если меньше, то на левом Докажем, что данный алгоритм работает за $O(n)$

Изобразим полученные блоки.

-	1	2	3	..	$i=\frac{n}{2}$	..	$\frac{n}{5}$
$1$	$a_{11}$	$a_{12}$	$a_{13}$	..	$a_{1i}$	..	$a_{1n}$
$2$	$a_{21}$	$a_{22}$	$a_{23}$	..	$a_{2i}$	..	$a2n$
$3$	$a_{31}$	$a_{32}$	$a_{33}$	..	$m$	..	$a3n$
$4$	$a_{41}$	$a_{42}$	$a_{43}$	..	$a_{4i}$	..	$a4n$
$5$	$a_{51}$	$a_{52}$	$a_{53}$	..	$a_{5i}$	..	$a5n$

В каждом столбце изображены блоки. Сверху наименьший в блоке элемент, снизу наибольший. Теперь отсортируем столбцы по медиане в каждом блоке(3 строке). Получим, что все элементы, расположенные выше и левее медины $m$ меньше $m$. А это $\frac{3n}{10}$ элементов.

В каждой строке $\frac{n}{5}$ элементов. Медиана в середине, поэтому $\frac{n}{10}$ элементов в строке меньше медианы. Таких строк 3 $\rightarrow$ $\frac{7n}{10}$ элементов.

$T(n) \leq T(\frac{n}{5}) + T(\frac{7n}{10}) + cn$

Теперь для детерменированного алгоритма быстрой сортровки используем теорему из прошлого занятия.

$T(n) = 2T(\frac{n}{2}) + \Theta(n)$

Резюмируем

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

Сортировка чисел

До этого момента мы говорили о сортировке объектов в общем виде. Теперь же поговорим о сортировке чисел в частности.

Сортировка подсчётом(Counting sort)

Пусть мы знаем, что все числа лежат в диапазоне от 0 до $k$ Тогда:

1. За один обход. Создадим массив счётчиков С, в который поместим, сколько раз встречается каждое из чисел.
2. Теперь вернёмся к началу массива и начнём его заполнять при помощи С, повторив каждый элемент С[i], где i-число от 0 до k

Например для $k=5$ Дан массив: A = [1,2,3,2,4,5] Инициализируем массив счётчиков: [0,0,0,0,0,0] После всех операций массив счётчиков будет равен: [0,1,2,1,1,1]

В таьлице ниже в столбце D текущий результат сортировки, в С - массив счётчиков:

D	C
[0,0,0,0,0,0,0]	[0,1,2,1,1,1]
[0,1,0,0,0,0,0]	[0,0,2,1,1,1]
[0,1,2,0,0,0,0]	[0,0,1,1,1,1]
[0,1,2,2,0,0,0]	[0,0,0,1,1,1]
[0,1,2,2,3,0,0]	[0,0,0,0,1,1]
[0,1,2,2,3,4,0]	[0,0,0,0,0,1]
[0,1,2,2,3,4,5]	[0,0,0,0,0,0]

Вся сортировка выполняется за $2\ O(n)$

Стабильные сортировки

Вместо сортировки чисел мы также можем сортировать более сложные структуры, но с числовым ключом. Вернёмся к нашей задаче с ранжированием игроков. Пусть у нас есть структура состоящая из 2 полей: заработанные монеты - $coins$ и кол-во очков - $score$. Нашей задачей является отсортировать всех игроков по $score$, зная что по $coins$ он уже отсортирован При этом, очевидно, что наша сортировка должна удовлетворять следующему требованию: если $score$ одинаковый, то по $coins$ значения не должны меняться местами, т.е для двух записей $\{score: 100, coins:125 \}, \{score:100, coins:150 \}$ После сортировке не должно быть $\{score:100, coins:150 \}, \{score:100, coins:125 \}$

Определение: Сортировка называется стабильной, если $\forall a_i = a_j, i<j$ после сортировки $\pi^{-1}(i) < \pi^{-1}(j)$ .

Так как $\pi$ перестановка принимает индекс в результирующем массиве и возвращает индекс в исходном, то $\pi^{-1}$ наоборот, принимает индекс исходного массива и возвращает индекс в итоговом.

Стабильная сортировка подсчётом

Сделаем нашу сортировку из раздела выше стабильной.

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

Будем использовать пример из предыдущего раздела A = [1,2,3,2,4,5], k=5

C	IndEnd
[0,1,2,1,1,1]	[0,0,0,0,0,0]
[0,0,2,1,1,1]	[0,1,0,0,0,0]
[0,0,0,1,1,1]	[0,1,3,0,0,0]
[0,0,0,0,1,1]	[0,1,3,4,0,0]
[0,0,0,0,0,1]	[0,1,3,4,5,0]
[0,0,0,0,0,0]	[0,1,3,4,5,6]

Теперь сместим на один блок и получим массив IndStart=[0,0,1,3,4,5]

Остался последний шаг. Будем проходить по исходному массиву слева направо и встретив число i, будем подставлять этот элемент на место IndStart[i] и затем увеличивать этот индекс на 1.

Начнём подставлять:

A	IndStart	D
[1,2,3,2,4,5]	[0,0,1,3,4,5]	[0,0,0,0,0,0]
[0,2,3,2,4,5]	[0,1,1,3,4,5]	[1,0,0,0,0,0]
[0,0,3,2,4,5]	[0,1,2,3,4,5]	[1,2,0,0,0,0]
[0,0,0,2,4,5]	[0,1,2,4,4,5]	[1,2,0,3,0,0]
[0,0,0,0,4,5]	[0,1,3,4,4,5]	[1,2,2,3,0,0]
[0,0,0,0,0,5]	[0,1,3,4,5,5]	[1,2,2,3,4,0]
[0,0,0,0,0,0]	[0,1,3,4,5,6]	[1,2,2,3,4,5]

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

Цифровая сортировка(Radix sort)

В предыдущем разделе мы нашли сортировку за линейное время, теперь уберем ограничения по размеру ключа(k).

Основная идея:

1. Отсортируемся по последней цифре числа при помощи любой стабильной сортировки.
2. Повторим процедуру для оставшихся цифр.

Так как цифр всего 9, то можно применить Counting sort для k=9. Алгоритм будет корректным, т.к. внутри применяется стабильная сортировка.

Резюмируем

Нам удалось разработать алгоритм, который позволяет отсортировать любые объекты за $O(n\ log\ n)$ в любом случае, а также сортировать данные по числовому ключу за $O(n)$