\documentclass[12pt]{article}

% План четвертой лекции
% Автор: Сергей Копелиович

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
%\usepackage{enumerate}
%\usepackage{hologo}
%\usepackage{color}
%\usepackage{picture}

\voffset=-20mm
\textheight=220mm
\hoffset=-20mm
\textwidth=175mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle} % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}
\def\myindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}

\newenvironment{MyTabbing}{
  \t\bgroup
  %\vspace*{-\baselineskip}
  \begin{tabbing}
    aa\=aa\=aa\=aa\kill
}{
  \end{tabbing}
  \t\egroup
}

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#4}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: сортировки} \\
  \vspace{0.5em}
  {\Large 23 сентября} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\vspace{1em}
\tableofcontents
%\pagebreak

\section{Квадратичные сортировки}

\begin{tabular}{|c|c|c|c|c|}
  \hline
    Название &
    \begin{minipage}[c]{2.6cm} Количество \\ сравнений \end{minipage} &
    \begin{minipage}[c]{2.6cm} Количество \\ копирований \end{minipage} &
    Стабильная &
    Память \\
  \hline
    Selection & $\Theta(n^2)$ & $\O(n)$ & \t{-} & $\O(1)$ \\
    Insertion & $\Theta(n+inv)$ & $\Theta(inv)$ & \t{+} & $\O(1)$ \\
    InsertionBS & $\Theta(n \log n)$ & $\Theta(inv)$ & \t{+} & $\O(1)$ \\
    Bubble & $\Theta(n^2)$ & $\O(n^2)$ & \t{+} & $\O(1)$ \\
    ShakerBubble & $\O(n^2)$ & $\O(n^2)$ & \t{+} & $\O(1)$ \\
    ShellSort & $\O(n \log^2 n)$ & $\O(n \log^2 n)$ & \t{-} & $\O(1)$ \\
  \hline
\end{tabular}

\section{Integer Sorting}

\subsection{Bucket Sort}
\myindent
Отсортируем $n$ целых чисел.

1. Найдем минимум $l$ и максимум $r$.

2. Разобьем числовую прямую на $n$ равных по длине полуинтервалов (buckets).

3. Положили каждое число $x_i$ в нужный bucket: $\lfloor\frac{r - x_i}{r - l + 1}\rfloor$.

4. Каждый bucket отсортируем. Если чисел мало, то InsertionSort, иначе BucketSort.

Сортировка устойчива. В среднем работает за $\Theta(n)$. В худшем за $\Theta(n\log_n{m})$.

\subsection{Radix Sort}
\myindent
Сортируем $n$ целых чисел от $1$ до $m$.

Сортировка подсчетом за $\Theta(n + m)$.

Сортировка чисел от $1$ до $n^2$ за  $\Theta(n)$.

Radix sort: сортировка чисел от $1$ до $m$ за $O(n \lceil\log_n m\rceil)$.

Сортировка чисел, как битовых строк, за $O(n \log_2 m)$.

Сортировка $n$ строк длины $L$ над алфавитом $\Sigma$ за $\Theta(\Sigma + nL)$

Сортировка длинных чисел: $O(n \lceil\log_n m\rceil^2)$.

\subsection{Сортировка чисел за $O(n \log_2\log_2 m)$}
\myindent
Kirkpatrick, Reisch'84 \cite{KIRK'84}

1. Пусть все числа не более $2^{2^k}$, то есть имеют длину $2^k$ бит.

2. $2^{2^k} \le n \SO $ отсортируем подсчетом за $\O(n + 2^{2^k}) = \O(n)$.

3. За $\O(n)$ перейдем к рекурсивному вызову сортировки от $(k-1)$: \begin{MyTabbing}
%   Sort(k, x) \{ \\
%   \> Если k не больше logn, запустили CountSort и вышли \\
%   \> Пусть $x_i = \q{(a_i,b_i),data_i}$ // длина $a_i$ равна $2^{k-1}$ \\
%   \> for ((a,b),data) in range(n): \\ 
%   \> \> list[a] += $\q{b,data}$; // list "--- это хеш-таблица, в каждой ячейке список \\
%   \> for (x,list[x]): // перебираем все бакеты \\
%   \> \> max[x] = extractMax(list[x]): // удалили max элемент из списка \\
%   \> \> for (b,data) in list[x]: \\
%   \> \> \> v += $\q{b,(x,data)}$; // сперва ключ, потом данные \\
%   \> \> v += $\q{x,(\t{-}1,\t{-}1)}$; // сперва ключ, потом данные \\
%   \> Sort(k - 1, v); // рекурсивный вызов \\
%   \> for (b,(a,data)) in v: \\
%   \> \> if a != -1: \\
%   \> \> \> sorted\_list[a] += $\q{b,data}$; \\
%   \> \> else: \\
%   \> \> \> sorted\_a += b; \\
%   \> for a in sorted\_a: \\
%   \> \> result += sorted\_list[a]; \\
%   \> \> result += max[a]; \\
%   \> return result \\
%   \}
   Sort(k, x) \{ \\
   \> if ($2^{2^k} \le n$) \{ CountSort(x); return; \} \\
   \> $x_i$ делим на две половины $a_i, b_i$ по $2^{k-1}$ бит каждая. \\
   \> для каждого $a$: \\
   \> \> насчитываем список всех парных $b$: ListB[a]. \\
   \> \> отщепляем от списка максимальный элемент: max[a], длина списка уменьшилась на один \\
   \> \> Sort(k-1, ListB[$a$]) \\
   \> создали список всех $a$: ListA \\
   \> Sort(k-1, ListA) \\
   \> перебираем $a$ в отсортированном порядке \\
   \> \> перебираем парные $b$ в отсортированном порядке \\
   \> \> \> result.push\_back(pair(a,b)) \\
   \> \> result.push\_back(pair(a,max[a])) \\
   \}
\end{MyTabbing}
Конец сортировки. Время на сортировку чисел от $1$ до $m$: $\Theta(n(\log\log{m} - \log\log{n}))$. \\

\subsection{Исторический экскурс}

\begin{tabular}{|c|c|c|c|c|}
  \hline
    Название &
    Время &
    Автор & Год \\
  \hline
    RadixSort & $\Theta(n \log_n m)$ & 1887 & Hollerith \\
    V.E.B. trees & $\Theta(n \log \log m)$ & 1975 & Van Emde Boas  \\
    - & $\Theta(n \log \log m)$ & 1984 & Kirkpatrick \\
    Fuzzy Trees & $\Theta(n \frac{\log n}{\log\log n})$ & 1990 & Fredman, Willard \\
    Fuzzy Trees & $\Theta(n \sqrt{\log n})$ & 1993 & Fredman, Willard \\
    Exponential Trees & $\Theta(n \log\log n)$ & 1995 & Andersson \\
    - & randomized $\Theta(n)$ & 1998 & группа авторов \\
    - & $\Theta(n \sqrt{\log\log n})$ & 1995 & Han, Thorup \\
  \hline
\end{tabular}

\section{Сортировки за $O(n \log n)$}

Из любой сортировки можно сделать стабильную.

MergeSort можно писать без рекурсии.

IntroSort = QuickSort + HeapSort + InsertionSort.

\subsection{Исторический экскурс}

\begin{tabular}{|c|c|c|c|c|c|c|c|}
  \hline
    Название &
    \begin{minipage}[c]{2.6cm} Количество \\ сравнений \end{minipage} &
    \begin{minipage}[c]{2.6cm} Количество \\ копирований \end{minipage} &
    Stable &
    Rand &
    Память &
    Автор &
    Год \\
  \hline
    QuickSort & $\Theta(n \log n)$ & $\Theta(n \log n)$ & \t{-} & \t{+} & $\Theta(\log n)$ & 1962 & Hoare \\
    IntroSort & $\Theta(n \log n)$ & $\Theta(n \log n)$ & \t{-} & \t{-} & $\Theta(\log n)$ & 1997 & Musser \\
    MergeSort & $\Theta(n \log n)$ & $\Theta(n \log n)$ & \t{+} & \t{-} & $\Theta(n)$ & 1948 & Neumann \\
    InplaceMergeSort & $\Theta(n \log^2 n)$ & $\Theta(n \log^2 n)$ & \t{+} & \t{-} & $\O(1)$ & 1977 & Pardo \\
    HeapSort & $\O(n \log n)$ & $\O(n \log n)$ & \t{-} & \t{-} & $\O(1)$  & 1964 & Williams \\
    AdaptiveHeapSort & $\O(n \log n)$ & $\O(n \log n)$ & \t{-} & \t{-} & $\O(n)$  & 1993 & Petersson \\
    InplaceMergeSort & $\O(n \log n)$ & $\O(n \log n)$ & \t{+} & \t{-} & $\O(1)$  & 1995 & Symvonis \\
    InplaceMergeSort & $\O(n \log n)$ & $\O(n \log n)$ & \t{+} & \t{-} & $\O(1)$  & 2008 & Kim, Kutzner \\
  \hline
\end{tabular}

\subsection{STL}

В \t{C/C++}: \\
sort = IntroSort = Quick + Heap + Insertion \\
stable\_sort = MergeSort with inplace\_merge (пытается выделить память, если не получается, делает merge за $\O(n\log n)$).

\subsection{Адаптивные сортировки}

AdaptiveHeapSort = построение декартова дерева + Heap \\
SplaySort = сортировка Splay деревом

\vspace*{0.5em}
AdaptiveHeapSort: \\
$\bullet$ Уже отсортированный в возрастающем или убывающем порядке сортируется за линию. \\
$\bullet$ Если массив можно разбить на $k$ возрастающих или убывающих подпоследовательностей, время сортировки $\O(n \log k)$ \\
$\bullet$ Если массив содержит $x$ инверсий, время сортировки $\O(n \log (\frac{x}{n}+2))$

\subsection{Точные оценки на число сравненией}

$\bullet$ Lower bound: $\log_2(n!) = n\log_2n - 1.44n$ \\
$\bullet$ Текущий оптимум: $n\log_2n - 1.38n$ (чистая теория) \\
$\bullet$ HeapSort при $n=2^k$: $Build + Sort = n + (n \log n - 2n) = n \log n - n$ \\
$\bullet$ MergeSort при $n=2^k$: $n(\log n - 1) - n = n \log n - 2n$ 

\subsection{InplaceMerge}

Reverse $\rightarrow$ Rotate $\rightarrow$ Partition $\rightarrow$ InplaceMerge за $\O(n{\log}n)$

\begin{thebibliography}{1}
  \bibitem{KIRK'84}
	\emph{Upper bounds for sorting integers on random access machines} \\
    David Kirkpatrick, Stefan Reisch, \quad
    TCS 28 (1984) 263-276
\end{thebibliography}

\end{document}
