Сортировка вставками

Мы решаем задачу сортировки: нам нужно упорядочить ключи K1,K2,…,KnK_1, K_2, \dotsc, K_n по возрастанию относительного какого-то линейного порядка.

Метод простых вставок

Допустим, мы уже отсортировали j−1j-1 записей так, что

K1⩽K2⩽⋯⩽Kj−2   ⁣⩽   ⁣Kj−1K_1 \le K_2 \le \dotsb \le K_{j-2} \;\! \le \;\! K_{j-1}

Теперь нам нужно вставить следующий ключ KjK_j. Будем сравнивать его по очереди с ключами Kj−1,Kj−2,…K1K_{j-1}, K_{j-2}, \dotsc K_1, пока не обнаружим, что его нужно вставить между ключами KiK_i и Ki+1K_{i+1}. Сдвинем все ключи, начиная с Ki+1K_{i+1}, на одну позицию и вставим запись KjK_j на место i+1i+1.

Другими словами, мы каждый раз берем новый ключ и вставляем его в правильное место.

function insertion_sort(mutable array a[n]): for int j = 1; j < n; j++: int i = j - 1 key = a[j] while i >= 0 and a[i] > key: a[i+1] = a[i] i -= 1 a[i+1] = key

Количество сравнений в этом алгоритме равно числу инверсий перестановки (K1,K2,…,Kn)(K_1, K_2, \dotsc, K_n) плюс количество выходных сравнений в цикле while — n−1n-1

min⁡=n−1,ave⁡=(n2+3n−4)/4,max⁡=(n2+n−2)/2,dev⁡=16n (n−1) (n+5/2)\min\limits = n-1 ,\quad \ave = (n^2 + 3n - 4) / 4 ,\quad \max\limits = (n^2 + n - 2) / 2 ,\quad \dev = \frac{1}{6}\sqrt{n \, (n-1) \, (n + 5/2)}

Количество записей (присваиваний элементов a) совпадает с количеством сравнений.

Бинарные и двухпутевые вставки

В алгоритме простых вставок новый jj-й элемент сравнивался в среднем с (j−1)/2(j-1)/2 уже отсортированными элементами по порядку. В итоге общее количество сравнений в среднем равно ∑j=2n(j−1)/2=(n2−n)/4=O(n2)\sum\limits_{j=2}^n (j-1)/2 = (n^2 - n) / 4 = O(n^2).

Можно использовать то, что элементы, в которые мы хотим вставить новый ключ, уже отсортированы. Будем искать место вставки с помощью бинарного поиска. До конца это проблему не решит, ведь кроме поиска места вставки нужно её произвести. Но даже так это неплохой буст к производительности

Итого мы для каждого элемента с номером j+1j+1 проводим бинарный поиск в подмассиве размера jj (все, что находится спереди). В итоге максимальное количество сравнений

∑j=1n−1(⌊log⁡2j⌋+1)=n⋅⌈log⁡2n⌉−2⌈log⁡2n⌉+1=nlog⁡2n−n+O(1)\sum\limits_{j=1}^{n-1} \bigl( \lfloor \log_2 j \rfloor + 1 \bigr) = n \cdot \lceil \log_2 n \rceil - 2^{\lceil \log_2 n \rceil} + 1 = n \log_2 n - n + O(1)

Мы получили, что количество сравнений близко к оптимальному, и это не может не радовать. Однако, наша сортировка всё равно выполняет O(n2)O \bigr( n^2 \bigr) записей, что сводит на нет все наши старания.

Проблема в том, что вставка в массив выполняется за O(n)O(n) записей. Вообще, не существует линейной структуры данных, обеспечивающей одновременно поиск и вставку быстрее, чем за O(n)O(n) операций. Можно использовать нелинейные структуры, например сбалансированные деревья поиска или список с пропусками, но тогда у нас будет нехилый временной оверхед на саму структуру.

Смягчить проблему можно, рассмотрев особый метод двухпутевых вставок.

Двухпутевые вставки

Выделим под массив участок памяти размером 3n3n, а сам массив поместим в середину. Будем поддерживать указатели на начало массива и его длину, чтобы не потерять массив в аллоцированном участке.

При вставке элемента в массив определяем, к какому краю ближе место вставки jj, и расширяем массив в сторону этого края, копируя min⁡(n−j,j)\min\limits(n-j, j) элементов вместо n−jn-j. Таким образом мы в 22 раза уменьшили ожидаемое количество записей, получив алгоритм со средним количество записей n2/8+O(n)n^2/8 + O(n) вместо n2/4+O(n)n^2/4 + O(n).

Блочные вставки

Есть способ немного сгладить проблему линейных структур данных. Нужно использовать блочный список.

Массив представляем в виде блочного списка с размером блока kk. Поиск в блочном списке длины nn занимает O(n/k+log⁡k)O(n/k + \log k) операций, а вставка занимает O(k)O(k) операций, если мы знаем, в какой блок вставлять (имеем на него ссылку).

Получается, что общее время работы алгоритма сортировки блочными вставками равно

∑j=1n(O(j/k+log⁡k)+O(k))=O(n2k+nlog⁡k+nk)\sum\limits_{j=1}^n \bigl( O(j/k + \log k) + O(k) \bigr) = O \left( \frac{n^2}{k} + n \log k + nk \right)

Минимум достигается при k=nk = \sqrt{n}, общее количество операций при сортировке блочными вставками получается равным O(n3/2)O \bigl( n^{3/2} \bigr).

Метод экзотический, имеет какой-то оверхед на структуру и не является широко универсальным, так как приходится следить за размерами блоков, совершать реаллокации и слияния.

Сортировка Шелла

Если в процессе сортировки мы перемещаем элементы на 11 позицию за операцию, время выполнение будет в любом случае Ω(n2)\Omega \bigl( n^2 \bigr).

Пусть σ∈Sn\sigma \in \S_n — случайная перестановка nn элементов массива.

Рассмотрим величину δj(σ)   ⁣=def   ⁣∣σ(j)−j∣\delta_j (\sigma) \defeq \bigl| \sigma(j) - j \bigr| — расстояние от элемента исходном массиве до его правильного положения в отсортированном массиве. Предположив равномерное распределение перестановок σ\sigma, найдём среднее

E⁡(δj(σ))=1n∑i=1n∣i−j∣=1n(j (j−1)2+(n−j) (n−j+1)2)\expect \bigl( \delta_j (\sigma) \bigr) = \frac{1}{n} \sum\limits_{i=1}^n |i-j| = \frac{1}{n} \Bigg( \frac{j \, (j-1)}{2} + \frac{(n-j) \, (n-j+1)}{2} \Bigg)

Полное расстояние перемещения — величина

D(σ)   ⁣=def   ⁣∑j=1nδj(n)=∑j=1n∣σ(j)−j∣D(\sigma) \defeq \sum\limits_{j=1}^n \delta_j (n) = \sum\limits_{j=1}^n \bigl| \sigma(j) - j \bigr|

Это сумма расстояний, на которые элементы уехали от своих правильных позиций при перестановке σ\sigma. Величина D(σ)D(\sigma) служит оценкой сложности предстоящего процесса сортировки.

Минимум считается просто: min⁡σ   ⁣∈   ⁣SnD(σ)=0\min\limits_{\sigma \;\! \in \;\! \S_n} D(\sigma) = 0 при σ=1\sigma = \1.

Максимум достигается на перестановке, которая максимально далеко перемещает каждый элемент. При чётном nn это полный разворот, а при нечётном nn надо центральный элемент оставить на месте. Итого max⁡σ   ⁣∈   ⁣SnD(σ)=⌊n2/2⌋\max\limits_{\sigma \;\! \in \;\! \S_n} D(\sigma) = \lfloor n^2 / 2 \rfloor.

Для подсчёта среднего значения воспользуемся результатом для величины δj(σ)\delta_j (\sigma):

E⁡(D(σ))=∑j=1nE⁡(δj(σ))=2n∑j=1n(j2)=n2−13\expect \bigl( D(\sigma) \bigr) = \sum\limits_{j=1}^n \expect \bigl( \delta_j (\sigma) \bigr) = \frac{2}{n} \sum\limits_{j=1}^n \binom{j}{2} = \frac{n^2-1}{3}

Для вычисления дисперсии необходимо сначала найти дисперсию δj(σ)\delta_j (\sigma) и ковариации расстояний для разных элементов, то есть для величин δi(σ)\delta_i (\sigma) и δj(σ)\delta_j (\sigma).

var⁡δj(σ)=1n∑i=1n(i−j)2−(1n∑i=1n∣i−j∣)2==1n(2(j3)+(j2)+2(n−j+13)+(n−j+12))−1n2((j2)+(n−j+12))2==−j4n2+2j3n−j2+n212+2j3n2−3j2n+j−j2n2+jn−112\align{ \var \delta_j (\sigma) &= \frac{1}{n} \sum\limits_{i=1}^n (i-j)^2 - \left( \frac{1}{n} \sum\limits_{i=1}^n |i-j| \right)^2 = \\ &= \frac{1}{n} \Biggl( 2 \binom{j}{3} + \binom{j}{2} + 2 \binom{n-j+1}{3} + \binom{n-j+1}{2} \Biggr) - \frac{1}{n^2} \Biggl( \binom{j}{2} + \binom{n-j+1}{2} \Biggr)^2 =\\[0.4em]&= - \frac{j^4}{n^2} + \frac{2j^3}{n} - j^2 + \frac{n^2}{12} + \frac{2j^3}{n^2} - \frac{3j^2}{n} + j - \frac{j^2}{n^2} + \frac{j}{n} - \frac{1}{12} }

Ковариацию придётся вычислять через разбиение суммы

cov⁡(δi(σ),δj(σ))=1n (n−1)∑1⩽k,l⩽nk≠l∣k−i∣⋅∣l−j∣=1n (n−1)(∑k=1n∑l=1n∣k−i∣⋅∣l−j∣−∑ℓ=1n∣ℓ−i∣⋅∣ℓ−j∣)==1n (n−1)(∑k=1n∣k−i∣⋅∑l=1n∣l−j∣−∑ℓ=1n∣ℓ−i∣⋅∣ℓ−j∣)\align{ \cov \bigl( \delta_i (\sigma), \delta_j (\sigma) \bigr) &= \frac{1}{n \, (n-1)} \sum\limits_{\substack{1 \;\! \le \;\! k, l \le n\\[0.4em]k \;\! \neq \;\! l}} |k-i| \cdot |l-j|\\[0.8em]&= \frac{1}{n \, (n-1)} \Biggl( \sum\limits_{k=1}^n \sum\limits_{l=1}^n |k-i| \cdot |l-j| - \sum\limits_{\ell=1}^n |\ell-i| \cdot |\ell-j| \Biggr) =\\[0.8em]&= \frac{1}{n \, (n-1)} \Biggl( \sum\limits_{k=1}^n |k-i| \cdot \sum\limits_{l=1}^n |l-j| - \sum\limits_{\ell=1}^n |\ell-i| \cdot |\ell-j| \Biggr) }

Давайте введем величину T(i,j)T(i, j), характеризующую совместную удалённость элементов массива от двух фиксированных элементов i,ji, j.

T(i,j)=∑ℓ=1n∣ℓ−i∣⋅∣ℓ−j∣T(i, j) = \sum\limits_{\ell=1}^n |\ell-i| \cdot |\ell-j|

T(i,j)=T(j,i)T(i, j) = T(j, i), поэтому можно предположить, что i>ji > j, разбить отрезок суммирования на 33 подотрезка, раскрыть модули в каждом подотрезке и найти представление T(i,j)T(i, j):

T(i,j)=(∣i−j∣+1)⋅(min⁡(i,j)2)+2(min⁡(i,j)3)++(∣i−j∣−1)⋅(∣i−j∣2)−2(∣i−j∣3)++(∣i−j∣+1)⋅(n−max⁡(i,j)+12)+2(n−max⁡(i,j)+13)\align{ T(i, j) &= \bigl( |i-j| + 1 \bigr) \cdot \binom{\min\limits(i,j)}{2} + 2 \binom{\min\limits(i,j)}{3} +\\[0.8em]&+ \bigl( |i-j| - 1 \bigr) \cdot \binom{|i-j|}{2} - 2 \binom{|i-j|}{3} +\\[0.8em]&+ \bigl( |i-j| + 1 \bigr) \cdot \binom{n - \max\limits(i,j) + 1}{2} + 2 \binom{n - \max\limits(i,j) + 1}{3} }

Далее, посчитав значение сумм

∑k=1n∣k−i∣=(i2)+(n−i+12)и∑l=1n∣l−j∣=(j2)+(n−j+12)\sum\limits_{k=1}^n |k-i| = \binom{i}{2} + \binom{n-i+1}{2} \quad\text{и}\quad \sum\limits_{l=1}^n |l-j| = \binom{j}{2} + \binom{n-j+1}{2}

выражаем ковариацию

cov⁡(δi(σ),δj(σ))=1n (n−1)(∑k=1n∣k−i∣⋅∑l=1n∣l−j∣−∑ℓ=1n∣ℓ−i∣⋅∣ℓ−j∣)=1n (n−1)(((i2)+(n−i+12))⋅((j2)+(n−j+12))−T(i,j))\align{ \cov \bigl( \delta_i (\sigma), \delta_j (\sigma) \bigr) &= \frac{1}{n \, (n-1)} \Biggl( \sum\limits_{k=1}^n |k-i| \cdot \sum\limits_{l=1}^n |l-j| - \sum\limits_{\ell=1}^n |\ell-i| \cdot |\ell-j| \Biggr)\\[0.8em]&= \frac{1}{n \, (n-1)} \Biggl( \Biggl( \binom{i}{2} + \binom{n-i+1}{2} \Biggr) \cdot \Biggl( \binom{j}{2} + \binom{n-j+1}{2} \Biggr) - T(i, j) \Biggr) }

Нужны все эти страшные формулы для расчёта дисперсии var⁡D(σ)\var D(\sigma)

var⁡D(σ)=∑j=1nvar⁡δj(σ)+2∑1   ⁣⩽   ⁣i<j⩽ncov⁡(δi(σ),δj(σ))=n49−13180n3−845n2+O(n)\var D(\sigma) = \sum\limits_{j=1}^n \var \delta_j (\sigma) + 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \cov \bigl( \delta_i (\sigma), \delta_j (\sigma) \bigr) = \frac{n^4}{9} - \frac{13}{180} n^3 - \frac{8}{45} n^2 + O(n)

Многочлен получен подставлением асимптотических оценок для всех компонент суммы. Если очень надо, можно подставить все формулы и посчитать точное значение дисперсии. В O(n)O(n), кстати, скрыто что-то около 0.4n+0.30.4 n + 0.3.

dev⁡D(σ)=n49−13180n3−845n2+O(n)=n23−13360n+O(1)\dev D(\sigma) = \sqrt{\frac{n^4}{9} - \frac{13}{180} n^3 - \frac{8}{45} n^2 + O(n)} = \frac{n^2}{3} - \frac{13}{360} n + O(1)

Можем заключить, что полное расстояние перемещения D(σ)D(\sigma) распределено в соответствии с

min⁡=0,ave⁡=n2−13,max⁡=⌊n22⌋,dev⁡=n23−13360n+O(1)\min\limits = 0 ,\quad \ave = \frac{n^2-1}{3} ,\quad \max\limits = \left\lfloor \frac{n^2}{2} \right\rfloor ,\quad \dev = \frac{n^2}{3} - \frac{13}{360} n + O(1)

Анализ величины D(σ)D(\sigma) показывает, что для эффективного метода сортировки вставками необходим механизм, который позволил бы перемещать элементы большими скачками.

Такой механизм предложил Дональд Льюис Шелл в 1959 году. На основе этого механизма построена сортировка Шелла.

Основная идея — разбивать элементы на пары так, чтобы расстояние между элементами в одной паре было равно степени двойки.

input mutable array[int] a[n] input array[int] h[t] for gap in h : for int j = gap; j < n; j++: current = a[j] i = j - gap while i >= 0 and current < a[i]: a[i + gap] = a[i] i -= gap a[i + gap] = current