\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage[a4paper,margin=2cm]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{algorithm2e}

\title{Пример описания алгоритма: поразрядная LSD}
\author{Хирьянов Тимофей Фёдорович}
\date{Лекция 3. Сортировки. Инварианты циклов}

\begin{document}

\maketitle

Это образец короткого текста про алгоритм: псевдокод, зачем метод устроен так, инвариант, асимптотика по времени и по памяти.
Домашнее задание устроено так же, но вы разбираете \textbf{вставки} или \textbf{выбор} --- какой именно, решает монетка, не этот файл.

\section*{Постановка}

Дан массив $A[0..n-1]$ целых неотрицательных ключей.
Каждый ключ записывается ровно в $d$ цифрах в системе счисления с основанием $R \ge 2$
(для десятичных чисел $R = 10$, для двоичных карточек с лекции $R = 2$).
Цифры нумеруем с младшей: $p = 0$ --- разряд единиц, $p = d-1$ --- старший.
Цифра номера $p$ ключа $x$ есть
\[
	\operatorname{digit}(x, p) = \bigl\lfloor x / R^{p} \bigr\rfloor \bmod R.
\]
Нужно упорядочить $A$ по неубыванию ключей.

\section*{Алгоритм}

\begin{algorithm}[H]
	\SetAlgoLined
	\DontPrintSemicolon
	\SetKwInput{KwIn}{Вход}
	\SetKwInput{KwOut}{Выход}
	\SetKwProg{Fn}{Функция}{:}{}
	\SetKwFunction{FDigit}{digit}
	\SetKwFunction{FCount}{stable\_count\_by\_digit}
	\SetKwFunction{FLSD}{LSD}
	\KwIn{массив $A[0..n-1]$; число разрядов $d$; основание $R$}
	\KwOut{тот же массив, упорядоченный по неубыванию ключей}
	\BlankLine
	\Fn{\FCount{$A$, $p$}}{
		создать $count[0..R-1]$, заполнить нулями\;
		создать $B[0..n-1]$\;
		\For{$i \leftarrow 0$ \KwTo $n-1$}{
			$count[\FDigit{$A[i]$, $p$}] \leftarrow count[\FDigit{$A[i]$, $p$}] + 1$\;
		}
		\For{$v \leftarrow 1$ \KwTo $R-1$}{
			$count[v] \leftarrow count[v] + count[v-1]$\;
		}
		\For{$i \leftarrow n-1$ \KwTo $0$}{
			$v \leftarrow \FDigit{$A[i]$, $p$}$\;
			$count[v] \leftarrow count[v] - 1$\;
			$B[count[v]] \leftarrow A[i]$\;
		}
		скопировать $B$ в $A$\;
	}
	\BlankLine
	\Fn{\FLSD{$A$, $d$, $R$}}{
		\For{$p \leftarrow 0$ \KwTo $d-1$}{
			\FCount{$A$, $p$}\;
		}
	}
	\caption{LSD: устойчивый подсчёт с младшего разряда}
\end{algorithm}

Обратный проход по $i$ нужен для \textbf{устойчивости}: среди ключей с одной и той же цифрой $v$ раньше во входном порядке окажется тот, кто стоял левее.

\section*{Почему так, а не со старшего}

Один устойчивый проход по цифре --- это сортировка подсчётом: ключ прохода --- маленькое целое $0..R-1$, индекс массива снова значит \emph{значение}, как частотный массив.
Сравнений «$a_i < a_j$?» нет, поэтому нижняя оценка $\Omega(n\log n)$ в модели сравнений сюда не относится.

Если начать со \emph{старшего} разряда, одинаковые префиксы придётся разбирать рекурсивно (MSD).
LSD идёт с младшего и полагается на устойчивость: следующий проход не имеет права переставлять тех, кто уже выстроился по младшим цифрам.
На лекции это была стопка карточек: палочка отделяет дырку «0» от «1», кто был выше при равной дырке, тот выше и остаётся.

\section*{Инвариант}

После $k$ проходов ($p = 0, \ldots, k-1$) массив упорядочен по числу из $k$ младших разрядов: если смотреть только цифры $0..k-1$, последовательность неубывающая.
При равных $k$ младших цифрах относительный порядок как во входе в этот набор проходов.

\begin{enumerate}
	\item \textbf{Инициализация.}
	При $k = 0$ «число из нуля цифр» у всех одинаково, инвариант пустой: массив --- перестановка входа.
	\item \textbf{Сохранение.}
	Пусть после $k$ проходов инвариант верен.
	Проход $p = k$ устойчиво раскладывает по цифре $k$.
	Ключи с меньшей цифрой $k$ уходят левее ключей с большей.
	Ключи с одной и той же цифрой $k$ сохраняют прежний относительный порядок, а он по предположению уже правильный по цифрам $0..k-1$.
	Значит, после прохода порядок правильный по цифрам $0..k$.
	\item \textbf{Завершение.}
	При $k = d$ учтены все разряды, массив упорядочен по полному ключу.
\end{enumerate}

\section*{Трассировка}

Четыре ключа в трёх битах, $R = 2$, $d = 3$: $A = [5,\,2,\,7,\,4]$, то есть $[101_2,\,010_2,\,111_2,\,100_2]$.

\begin{align*}
	\text{старт: }& [5,\,2,\,7,\,4] && 101,\;010,\;111,\;100 \\
	\text{после } p=0\text{: }& [2,\,4,\,5,\,7] && 010,\;100,\;101,\;111 \\
	\text{после } p=1\text{: }& [4,\,5,\,2,\,7] && 100,\;101,\;010,\;111 \\
	\text{после } p=2\text{: }& [2,\,4,\,5,\,7] && 010,\;100,\;101,\;111
\end{align*}

После первого прохода младший бит идёт $0,0,1,1$ --- как на карточках.
После второго прохода правильны уже два младших бита: $00,01,10,11$ в порядке $4,5,2,7$ ($100,101,010,111$).
Третий проход собирает старший бит, не ломая младшие: $2$ с префиксом $0$ встаёт перед четвёркой с префиксом $1$.

\section*{Асимптотика}

Один вызов \texttt{stable\_count\_by\_digit}: два прохода по $n$ элементов и один по $R$ счётчикам, то есть $\Theta(n + R)$ времени.
Таких вызовов $d$, итого
\begin{align*}
	T(n, d, R) &= \Theta\bigl(d(n + R)\bigr).
\end{align*}
Для двоичных карточек $R = 2$ это $\Theta(dn)$.
Для десятичных ключей из $d$ цифр --- $\Theta\bigl(d(n + 10)\bigr)$.
При фиксированном $d$ и $R$ время линейно по $n$.

Дополнительная память: массив $count$ длины $R$ и буфер $B$ длины $n$.
Между проходами их можно использовать повторно, поэтому сверх входа
\begin{align*}
	M_{\text{extra}}(n, R) &= \Theta(n + R).
\end{align*}
Сам массив $A$ занимает $\Theta(n)$ ячеек (или $\Theta(nd)$, если считать хранение всех цифр ключа).
На месте, без $\Theta(n)$ буфера, устойчивый подсчёт тем же способом не делается: обратный проход пишет в $B$.

\end{document}