	\Section{Сортировки, продолжение}{28 сентября}{Тонких}

\Subsection{Время работы рандомизированного QSort.}

\begin{Thm}{\emph{среднее время работы QSort: $\Theta(n \log n)$}}

	\THE{Доказательство \#1:}

		Докажем по индукции, что $T(n) \le C \cdot n \cdot \ln n$ 

		База : $T(2) \le C \cdot 2 \cdot \ln 2$

		Переход :

		Оценим матожидание времени работы:

		$T(n) \le \frac 1 n \cdot \sum\limits_{x = 1}^{n - 1}(T(x) + T(n - x - 1)) + n$

		Заметим, что $x$ и $n - x - 1$ пробегают одни и те же значения.

		$\SO T(n) \le \frac 1 n \cdot \sum\limits_{x = 1}^{n - 1}(2 \cdot T(x)) + n$

		$x < n \SO$ по предположению индукции $T(x) = C \cdot x \cdot \ln x$

		$\SO T(n) \le \frac 2 n \sum\limits_{x=1}^{n - 1}(C \cdot x \cdot \ln x) + n 
		\le \frac 2 n \int\limits_{1}^{n}(C \cdot x \cdot \ln x)dx + n$

		Посчитаем неопределенный интеграл:

		$\int (x \ln x)dx = \frac 1 2 x^2 \ln x - \int (\frac 1 2 x)dx = \frac 1 2 x^2 \ln x - \frac 1 4 x^2$

		Таким образом:

		$T(n) \le \frac 2 n \cdot C \cdot (\frac 1 2 n^2 \ln n - \frac 1 4 n^2 + \frac 1 4)
		= C \cdot (n \ln n - \frac 1 2 n + \frac {1} {2n}) + n = C n \ln n - \frac{Cn}{2} + \frac{C}{2n} + n$

		$\lim\limits_{n \to \infty} \frac{C}{2n} = 0$

		При $C = 2, n \to \infty: (-\frac{Cn}{2} + \frac{C}{2n} + n) = 0 \SO T(n) \le 2 \cdot n \ln n$

	\THE{Доказательство \#2:}

		Замечание: каждые два элемента сравниваются не более 1ого раза.

		Обозначим за $sa[i]$ $i$'ый элемент отсортированного массива.\\

		$T(n)$ = кол-во сравнений $( < )$ = $\sum\limits_{i, j} \chi (i, j)$, где $\chi (i, j) = 1$, если элементы $sa[i]$ и $sa[j]$ сравнивались и $\chi (i, j) = 0$ в противном случае.

		Заметим, что время работы зависит от какого-то рандома. Обозначим количество возможных исходов за $\alpha$. Все исходы равновероятны. Тогда матожидание времени работы равно среднему времени по всем возможным исходам.

		$T(n) = \frac{1}{\alpha} \sum\limits_{R=1}^{\alpha}(\sum\limits_{i, j}(\chi(i, j, R)))
		= \sum\limits_{i, j}(\frac{1}{\alpha} \sum\limits_{R=1}^{\alpha}(\chi(i, j, R))) 
		= \sum\limits_{i, j} Pr(sa[i]\mbox{ сравнивалось с }sa[j])$, где $Pr(...)$ - вероятность события (англ. $Probability$).\\

		Посчитаем $Pr(i, j)$:

		Все сравнения происходят только с барьерным элементом $(x)$ в Partition. 
		
		Рассмотрим момент, когда $sa[i]$ и $sa[j]$ попадают в разные ветви:

		$min(sa[i], sa[j]) \le x \le max(sa[i], sa[j])$. Всего на этом отрезке $|i - j| + 1$ чисел. Сравнение происходит только в случае, если $x = sa[i]$ или $x = sa[j]$. Итого $|i - j| + 1$ равноверотных исхода, в 2 из которых происходит сравнение. 

		$Pr(i, j) = \frac{2}{|i - j| + 1}$\\

		Тогда получаем:

		$T(n) = \sum\limits_{i, j} (\frac{2}{|i - j| + 1}) = \Theta(n \cdot \ln n)$
\end{Thm}

\Subsection{Порядковая статистика.}

	Пусть дан массив $a$ длиной $n$ и число $k$. Задача заключается в том, чтобы найти в этом массиве $k$-ое по величине число, т.е. $k$-ую порядковую статистику. %copied from e-maxx/algo

	В c++ : std::nth\_element(a.begin(), a.end(), k)

	Умеем получать за $\Theta(n \log n): sorted(a)[k]$

	Хотим за $\Theta(n)$

	Главная идея: QSort с одной веткой.

	Псевдокод:
	\begin{code}
nth_element(arr, k):
	x = arr[rand]
	l, r = partition(arr, x)
	
	#[0, l) - < x 
	#[l, r) - = x
	#[r, len) - > x

	if k <= l:
		return nth_element(arr[0..l - 1], k)
	else if k > r:
		return nth_element(arr[r..len - 1], k - r)
	else:
		return x
	\end{code} 

	Оценим среднее время работы(матожидание):

	$T(n) = \frac 1 n (\sum\limits_{x=0}^{n - 1} T(x)) + n 
	\le \frac{n(n - 1)}{2} \cdot \frac{C}{n} + n 
	\le \frac{n - 1}{2} \cdot C + n 
	\le C \cdot n$

\Subsection{Детерменированный (почти) QSort.} 

	IntroSort = std::sort()

	QSort + HSort + ISort

	Если глубина QSort $> 4n \SO HSort$

	Если $n < 8 \SO ISort$


