%\author{Савон Юлия}
%\date{13 октября 2015}
\Section{Kirkpatrick's Sort(1984)}{5 октября}{Савон Юлия}

\Subsection {Время работы Bucket Insertion Sort(BI)}
%\mysection{Теорема:}При рандоме [0..M] BI работает за $\Theta(n)$.

\begin{proof}
	Т.к. мы разделяем весь массив на Backets, а затем сортируем каждый backet отдельно. Тогда суммарное время сортировки $n + \sum{k_i^2}$, где $k^2_i$ - размер i-го backet.
\end{proof}

$\sum{k_i^2 = \sum_{1 \leqslant i, j \leqslant n} IS(i, j)}$, IS узнает лежат ли i, j в одном Backet

{\it Обозначения:}

{\bf Def 1:} E - среднее или мат-ожидание

{\bf Def 2:} Pr - вероятность (Probabilety)

$E(\sum{k_i^2})= E(\sum_{1 \leqslant i, j \leqslant n}{IS(i, j)}) = \Pr(IS(i, j)) = 1 \cdot \frac{1}{n} + \frac{1}{n} \cdot n \cdot (n - 1) = 2 \cdot n - 1$

{\it Реализация:}

1)Min, Max

2)$x_i \longrightarrow \lfloor \dfrac{x_i - Min}{Max - MIn + 1} \cdot n \rfloor$  

\pagebreak

\Subsection{Kirkpatrick's Sort (1984)}

{Задача:}
Имеется N целых чисел от 0 до $M - 1$, необходимо отсортировать их за $\mathcal{O}(N\log_2{\log_2{M}})$ \\
{Идея:} У нас уже есть RadixSort, которая работает за $\mathcal{O}(N\log_2{M})$ \\

\includegraphics[scale=0.6]{savon/New.png}

Для такого спуска необходимо совершать рекурсивные вызовы. \\
$a_i$ и $b_i$ - 2 половины массива знаков, n - количество чисел, k - длина чисел(для удобства будет считать, что $k = 2^s$, если не хватает, добавить 0 в начало)

{Псевдокод:} 

\lstinputlisting{savon/a.cpp}

{\it Оптимизация:} Вместо 2-х сортировок сделаем одну.

Для ассимптотики берем n, т.к. k не меняется.

$T(k) = 2T(\frac{k}{2}) + n = n \cdot \log_2{M}$

$\downarrow$

$T(k) = T(\frac{k}{2}) + n = n \cdot \log_2{k} = n \cdot \log_2{\log_2{M}}$ \\ \\ \\

1) $List[a_i] \leftarrow Hash Table$ (Для каждого $a_i$ - список $b_i$) $// \theta(n)$

\lstinputlisting{savon/b.cpp}

2)List[$a_i$].Find $\&$ Del Max Element (Для каждой находим и удаляем) $// \Theta(n)$

$\Rightarrow$ Кол-во списков(t) + Суммарное Длина(n - t) = n (итого n)

3)Рекурсивный вызов: Передаём сразу пару чисел $<b_i, a_i>$(n - t) или $<a_i, IND>$ (t) - 2 вида пар(IND - число которое не может точно попасться, для отличия пар) 

Сортируем только по 1-й половине. Первые половины ключи.

4)Результат рекурсии 

1.Sorted($a_i$)

2.Sorted List[$a_i$](список отсортирован) - списоу без MAX

5)Sorted List[$a_i$] += Max[$a_i$] (сливаем с MAX)

6)\lstinputlisting{savon/c.cpp}
