	\Section{Сортировки}{28 сентября}{Плющенко}
	\Subsection{Что хотим?}
		Есть массив a[] (индексация  [0, n) ), хотим получать массив b[], являющийся такой перестановкой a[], что элементы в нём упорядочены (обычно по неубыванию).
	
	\Subsection{Свойства сортировок}
	\begin{enumerate}
		\item Stable (устойчивость)
			
			Сортировка устойчива, если равные элементы из a[] сохранили порядок следования относительно друг друга в b[].
		\item Inplace (с использованием O(1) дополнительной памяти)
		
			Если сортировка использует O(1) дополнительной памяти (в частности, отсортированный массив сохраняется в a[]), то сортировка inplace.
	\end{enumerate}
	\Subsection{Сортировки за O($n^2$)}
	\begin{enumerate}
		\item Selection sort (Сортировка выбором)
	
			Делаем n итераций. На i-той итерации меняем местами a[i] и a[k], где k - индекс максимального элемента среди \{a[i], a[i + 1], ..., a[n - 1]\}, то есть выбираем, какой элемент будет i-тым в отсортированном массиве.
			
			Псевдокод:
			\begin{code}
for i in [0, n)
	k = index_of_max(a[i], a[i + 1], ..., a[n - 1])
	swap(a[i], a[k])
			\end{code}
			
			Количество сравнений - O($n^2$).
			
			Количество копирований элементов (swap'ов, присваиваний и т.п.) - O(n).
		\item Insertion sort (Сортировка вставками)
			
			Делаем n итераций. Элемент a[i] проталкиваем влево, пока он не окажется на своём месте в отсортированном массиве из первых i элеметов, то есть вставляем a[i] в нужное место отсортированного массива из первых (i - 1) элементов.
			
			Псеводкод:
			
			\begin{code}
for i in [0, n)
	j = i
	while (j > 0) && (a[j] < a[j - 1])
		swap(a[j], a[j - 1])
		j--
		//I-- 
			\end{code}
			Заметим, что каждый swap уменьшает на 1 кол-во инверсий I в массиве (инверсия - наличие такой пары a[i] и a[j], что (i < j) \&\& (a[i] > a[j])).
			
			Количество сравнений - O(n + I).
					
			Количество копирований элементов (swap'ов, присваиваний и т.п.) - O(I).
			
			\THE{Оптимизация}
			Так как мы вставляем в отсортированный массив, то можно позицию вставки искать бинпоиском (а затем "хвост" выталкивать вправо).
			
			Количество сравнений - O(min(n + I, nlogn)).
						
			Количество копирований элементов (swap'ов, присваиваний и т.п.) - O(I).
	\end{enumerate}
	\Subsection{Теорема}
	\begin{Thm}
		Не существует сортировок, использующих только сравнение "<" (никакой дополнительной информации про элементы массива), работающих за o(nlogn).
				
		\THEE{Доказательство.} Для простоты положим, что мы сортируем перестановку (то есть все элементы различны). Пусть наша сортировка сделала k сравнений (a[i] < a[j]), результат каждого - это 0 или 1, если False или True соответственно. Получили $2^k$ бинарных строк. Мы хотим уметь "отличать" друг от друга все перестановки нашего массива с помощью этих k сравнений, тогда должно выполняться $(n! \leq 2^k)$ (а иначе будут существовать 2 различных перестановки, которым соответствует одинаковый набор сравнений, а значит, мы не сможем эти две перестановки "отличить"). Логарифмируем обе части по основанию 2, получаем $\Theta(nlogn) \leq k$. То есть нам требуется хотя бы $\Theta(nlogn)$ сравнений, чтоб отсортировать массив.
	\end{Thm}	
	\Subsection{Сортировки за O(nlogn)}.
	\begin{enumerate}
		\item Merge sort (Сортировка слиянием)
		
		Спускаемся в левую и правую половину, сортируем их, сливаем две отсортированных половины.	
		
			\THE{Рекурсивная реализация}
			
			Псевдокод:
			\begin{code}
Merge sort(l, r) // [l, r)
	if (l + 1 >= r)
		return
	m = (l + r) / 2
	Merge sort(l, m)
	Merge sort(m, r)
	Merge(l, m, r)	// [l,m) + [m, r) -> [l, r)		
			\end{code} 
			Оценим время работы:
		
			T(n) = 2 $\cdot$ T($\frac{n}{2}$) + O(n) = O(nlogn) + O(n) $\cdot$ time\_for\_recursion.
			Оценим дополнительную память: 
			
			Add\_memory = memory\_for\_merge + O(logn) $\cdot$ memory\_for\_recursion. 
			
			Избавимся от рекурсии.
			
			\THE{Нерекурсивная реализация}
			
			Будем поддерживать отсортированными все куски длиной 1, 2, 4, ..., $\frac{n}{2}$ на соответствующей итерации и сливать их.
			
			Псевдокод:
			\begin{code}
for (k = 0; (1 << k) < n; k++)
	for (i = 0; i < n; i += 1 << (k + 1))
		Merge(i, min(i + (1 << k), n), min(i + (1 << (k + 1)), n)
			\end{code}
			Оценим время работы:
				
			T(n) = O(nlogn)
			
			Оценим дополнительную память: 
				
			Add\_memory = O(n) (для слияния).
			
			Нам достаточно двух массивов длины n. Поддерживаем куски длины 1 в a[], сливаем их в b[]. Теперь в b[] у нас куски длины 2. Сольём их в a[] и т.д.
				
			\Subsubsection{Merge с подсчётом инверсий}
			
			Псевдокод:
			\begin{code}
Merge(an, a, bn, b, c) // [a, a + an) + [b, b + bn) -> c
	i = j = I = 0
	for k in [0, an + bn)
		if (i < an) && ((j == bn) || (a[i] <= b[j]))
			c[k] = a[i++]
		else
			c[k] = b[j++]
			I += an - i					
			\end{code}
		\item Quick sort (Быстрая сортировка)
		Выбираем опорный элемент x, все элементы массива, которые <x, переносим в левую часть, все элементы массива, которые >x, переносим в правую часть, сортируем левую и правую части (partition).
		
		Псевдокод:
		
		\begin{code}
Qsort (a)
	if (a.size() <= 1)
		return
	x = a[rand % a.size()]
	return Qsort(<x_from_a) + x * count(a, x) + Qsort(>x_from_a)		
		\end{code}
		
		Оценим время работы (на перестановке):
		
		$T(n) = \frac{\sum_{x = 1}^{n - 1}(T(x) + T(n - x - 1))}{n} = O(nlogn)$
	\end{enumerate}
