\Section{Inplace алгоритмы}{5 Октября}{Привалихин}

\Subsection{Уже известные.}

\begin{MyList}
	\item QuickSort.
	
	\item HeapSort.
	
	\item SelectionSort.
	
	\item Partition.
	
	\item nth\_element.
	
	\item binary\_search.
	
	\item lower\_bound.
\end{MyList}

\Subsection{Reverse.}

Функция, разворачивающая массив задом наперед.
\begin{code}
void reverse(int *a, int n)
{
	int tmp;
	for (int i = 0; i <= n >> 1; i++)
	{
		tmp = a[i];
		a[i] = a[n - i - 1];
		a[n - i - 1] = tmp;
	}
	return;
}
\end{code}

\Subsection{rotate.}

\Subsubsection{1 способ. 3 reverse}

Пусть есть массив a длины n и нужно получить его циклический сдвиг на k. Это значит, что нужно, чтобы первые k элементов оказались в конце массива, сохранив порядок внутри, а остальные, соответственно, в начале, также сохранив порядок внутри. Для этого достаточно сделать reverse(a, k), reverse(a + k, n - k), reverse(a, n), так как после reverse(a, n) первые k элементов окажутся в конце, но при этом обе части массива - с n - k до n и с 0 до n - k - окажутся развернутыми.
\begin{code}
void rotate(int *a, int n, int k)
{
	reverse(a, k);
	reverse(a + k, n - k);
	reverse(a, n);
	return;
}
\end{code}

\Subsubsection{Способ 2.}

Пусть k = 1. Тогда можно запомнить первый элемент, затем положить по очереди во все элементы, кроме последнего, значение следующего элемента, затем присвоить последнему элементу запомненное значение.
Примечание: пока k = 1, параметрs start и k в функции не нужны. Зато потом пригодятся.
\begin{code}
void rotateone(int *a, int n, int k = 1, int start = 0)
{
	int i = start, i1;
	int tmp = *a;
	do
	{
		i1 = i;
		i += k;
		if (i > n)
			i -= n;
		a[i1] = a[i];
	}
	while (i != start);
	a[i1] = tmp;
}
\end{code}
Теперь избавимся от ограничения k = 1. Заметим, что все элементы массива разобьются на g = gcd(n, k) циклов, причем первые g элементов лежат в разных циклах. Также заметим, что внутри цикла произвести сдвиг можно, используя функцию rotateone.
\begin{code}
void rotate(int *a, int n, int k)
{
	g = gcd(n, k);
	for (int i = 0; i < g; i++)
	{
		rotateone(a, n, k, i);
	}
}
\end{code}
Также, в C++ реализована функция rotate, ее код можно посмотреть, при желании.

\Subsection{unique, intersect\_sets, diff\_sets}

Первая функция принимает на вход мультимножество в виде отсортированного массива и складывает в начало массива все неповторяющиеся элементы мультимножества, также в отсортированном порядке.
Поймем, что в отсортированном массиве одинаковые элементы могут идти только подряд. Тогда код unique становится очевиден:
\begin{code}
void unique(int *a, int n)
{
	int k = 0;
	for (int i = 0; i < n; i++)
		if (i == 0 || a[i] != a[i - 1])
			a[k++] = a[i];
	return;
}
\end{code}
intersect\_sets и diff\_sets реализуются аналогично.

\Subsection{merge}

Cлияние отсортированных массивов.

\Subsubsection{Пара общих идей}

Во-первых, для всех следующих алгоритмов требуется, чтобы два сливаемых массива были записаны подряд (то есть nums[0:n] = A, nums[n:n + k] = B).
Во-вторых, два подряд идущих массива можно поменять местами, используя rotate.

\Subsubsection{$O(N\log{N})$, Stable}

Предположим, что $|B| >= |A|$ (Если нет, их можно поменять местами за линейное время).
Рассмотрим элемент $x = B[\frac{|B|}{2}]$. Каждый массив можно разделить на три части - элементы, меньшие x ($A_1$, $B_1$), элементы равные x ($A_2$, $B_2$) и элементы большие x ($A_3$, $B_3$). Расположим эти части в порядке $A_1 B_1 A_2 B_2 A_3 B_3$, используя rotate. Теперь рекурсивно запустимся, чтобы слить $A_1$ с $B_1$ и $A_3$ с $B_3$. Теперь, если обозначить |A| + |B| за N, то время работы можно описать так:
$T(N) = T(X) + T(Y) + O(N)$, то есть $O(N\log{N})$, так как $X + Y \le N$ и $max(X, Y) \le \frac{3N}{4}$, так как хотя бы половина массива B больше x, а |B| - хотя бы $\frac{N}{2}$.
Примечание: так как мы используем рекурсию глубиной $\log{N}$, мы таки используем $О(\log{N})$ памяти.

\Subsubsection{O(N), Unstable}

	Cначала предположим, что все элементы различны, а также, что существует k такое что $N = k^2$, а также $|B| \vdots k$ и $|A| \vdots k$. Тогда весь массив можно разделить на куски длины k. Пронумеруем для удобства куски массива А и куски массива В отдельно с единицы. Нулевым куском назовем пустой массив. Отсортируем их с помощью SelectionSort по первому элементу (Сложность - $O(\sqrt{N}^2) = O(N)$, но при этом только $O(\sqrt{N})$ операций копирования, каждая из которых делается за $O(\sqrt{N})$. Теперь достаточно поочередно слить соседние куски (Сначала первый со вторым, затем третий с тем, что лежит на месте второго и так далее). Доказательство: Пусть i и j - максимальные числа такие, что $A_i$ и $B_j$ уже подвергались слиянию (изначально одно из чисел равно 1, второе 0). Тогда так как массивы A и B изначально были отсортированы, все $A_k$ для k < i и $В_k$ для k < j также уже подвергались слиянию. Более того, среди всех элементов, подвергавшихся слиянию, первые (i + j - 1) * k уже стоят на своих местах. Пусть первый неслитый кусок - $B_{j + 1}$. Тогда среди уже слитых элементов есть k * j элементов, меньших минимума из $B_{j + 1}$ - элементы $B_{k}$ для k < j + 1. Также, поскольку куски были отсортированы по первым элементам, а также все куски внутри отсортированы, минимум из $B_{j + 1}$ больше, чем минимум из $A_{i}$, который, в свою очередь, больше всех элементов $А_{k}$ для k < i. Значит, не более k элементов из начала стоят не на своих местах, причем это последние k элементов. Заметим, что на этом этапе алгоритм использует обычный merge за O(n), не inplace. Чтобы избавиться от этого, заметим, что последние 2 * k элементов можно использовать как буфер для merge, так как можно не копировать элементы, а менять местами. Именно в этот момент алгоритм перестает быть стабильным, так как элементы из буфера возвращаются туда в случайном порядке. Также, теперь последние 2 куска мы не сливаем с предыдущими. Теперь мы в конце просто сортируем SelectionSort-ом последние 3 * k элементов, что все равно работает за O(N).\\
	Теперь избавимся от предположения, что N - точный квадрат. Теперь, если взять k максимальное такое, что его квадрат не больше N, и снова поделим массивы А и В на куски длины k, то получится, что в конце каждого массива остался "хвост". Воспользовавшись функцией rotate, перенесем оба "хвоста" в конец, а для остальной части массивов применим описанный выше алгоритм. Теперь рассмотрим суммарную длину "хвостов". Она небольшая ($(x + y) < 2 * k$), где x и y - длины "хвостов". Значит, можно просто:
	\begin{MyList}
	\item поменять местами последние x + y элементов с предыдущими x + y элементами. Теперь последние x + y элементов отстоят от своих позиций в отсортированном массиве не более чем на 2 * k.
	\item Отсортировать 2 * k элементов, лежащих перед новым "хвостом". 
	\item Использовать описанный выше merge для слияния начала массива с последними 2 * k элементами перед новым "хвостом".
	\item Теперь можно просто отсортировать SelectionSort-ом последние 2 * k + x + y элементов.
	\end{MyList}
