Сортировки. Внутренние сортировки (1)

Понятие
Сортировать - распределять, разбирать по сортам, качеству, размерам, по сходным признакам. (толковый словарь Ожегова)
синонимы: классификация, систематизация.
перегруппировка элементов в некотором определенном порядке (упорядочивание, ранжирование).

Классы сортировок
сортировка массивов
сортировка (последовательных) файлов.
или
внутренняя сортировка
внешняя сортировка

Определение
Частичным порядком на множестве S называется такое бинарное отношение R, что для любых а, b и с из S
aRa (R рефлексивно),
aRb и bRc => aRc (R транзитивно),
aRb и bRa => a=b (R антисимметрично).

Определение
Линейным, или полным, порядком на множестве S называется такой частичный порядок R на S, что для любых двух элементов a, b выполняется либо aRb, либо bRa (другими словами, элементы a, b сравнимы)

Задача сортировки
Пусть дана последовательность из n элементов а1 , а2 , … , аn , выбранных из множества, на котором задан линейный порядок.
элемент аi назовем записью,
линейный порядок будем обозначать ≤
Каждая запись аi имеет ключ ki , который управляет процессом сортировки.
помимо ключа, запись может иметь некоторую дополнительную информацию, которая не влияет на процесс сортировки, но всегда присутствует в этой записи.

Задача сортировки
Требуется найти такую перестановку π = (π(1), π(2),…, π(n)) этих n записей, после которой ключи расположились бы в неубывающем порядке:
k π (1) ≤ k π(2) ≤… ≤ k π(n)

Определение
Алгоритм сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов одинаковыми ключами не изменяется предполагается, что элементы уже были отсортированы по некоторому вторичному ключу)
π(i) < π(j), если k π (i) ≤ k π(j) и i < j.

Сортировки
Все алгоритмы сортировки можно разбить на три группы:
сортировка с помощью включения,
сортировка выбором,
сортировка с помощью обменов

Сортировка с помощью включения
Пусть элементы а1 , а2 , … , аi-1 , ; 1 < i ≤ n уже упорядочены на предыдущих этапах данным алгоритмом.
На очередном этапе необходимо взять элемент аi , и включить в нужное место уже упорядоченной последовательности а1 , а2 , … , аi-1 .

Сортировка с помощью включения
В зависимости от того, как происходит процесс включения элемента, различаю прямое включение и двоичное включение.

Алгоритм сортировки с помощью прямого включения
Алгоритм insertion (a, n);
Input: массив А, содержащий n чисел (n≥1).
Output: упорядоченный массив A.
for i ← 2 to n {
x ← a[i]; a[0] ← x; j ← i;
while (x.key < a[j-1].key) {
a[j] ← a[j-1]; j ← j-1
}
a[j] ← x;
}

Пример

Оценка трудоемкости алгоритма

Алгоритм двоичного включения
Алгоритмinsertion2(a, n);
for i ← 2to n{
x ← a[i]; L ←1; R ← i;
while (L < R) {
m=[(L+R)/2];
if (a[m].key< x.key) {L ←m + 1}
else R ←m;
}
for j ←i downto (R + 1){
a[j] ←a[j -1];}
a[R] ← x;
}

Алгоритм двоичного включения

Сортировка выбором
Идея сортировки заключается в следующем:
1.Выбрать элемент с наименьшим ключом и поменять его с первым элементом. Теперь первый элемент стоит на своем месте.
2.Повторить действия с оставшимися n-1 элементами.
3.Процесс заканчивается, когда n -1 элементов будут помещены на свои места.

Сортировка выбором
Алгоритм selection (a, n);
for i ← 1to n-1{
k ← i;
for j ← i+1to n{
if a[j].key< a[k].key {
k ← j;
}
a[i]↔a[k];
}

Оценка трудоемкости алгоритма
В худшем случае:
T(n)=Cn+T(n-1), T(1)=0;
T(n)=Θ(n2)

Сортировка с помощью обменов
Сортировки помощью обменов основываются на сравнении двух элементов.
Если порядок элементов не соответствует упорядоченности, то происходит их обмен.
Процесс повторяется до тех пор, пока элементы не будут упорядочены.

Сортировка с помощью обменов
Пузырьковая сортировка
Шейкерная сортировка

Пузырьковая сортировка
Просматриваем исходную последовательность справа налево и на каждом шаге меньший из двух соседних элементов перемещается в левую позицию.
В результате первого просмотра самый маленький элемент будет находиться в крайней левой позиции.
После чего повторяем описанный выше процесс, рассматривая в качестве исходной последовательности массив, начиная со 2-ой позиции и т.д.

Пузырьковая сортировка
Алгоритм bubble_sort (a, n);
for i ← 2to n {
for j ← n downto i {
if (a[j-1].key> a[j].key){
a[j-1]↔a[j];
}
}
}

Шейкерная сортировка
Анализ алгоритма пузырьковой сортировки приводит к следующим наблюдениям:
Если при некотором из проходов нет перестановок, то алгоритм можно завершить.
Если зафиксировать индекс k последнего обмена (все пары левее этого индекса уж упорядочены), то просмотр можно завершить на этом индексе, а не идти до нижнего предела для индекса i.
Чередование направлений для просмотра (всплываетсамый легкий,тонет самый тяжелый).

Шейкерная сортировка
Алгоритм shaker_sort (a, n);
L ← 2; R ← n; k ← n;
repeat
for j ← Rdown to L
if (a[j-1].key> a[j].key){
a[j-1]↔a[j]; k ← j;
}
L ← k+1;
for j ← Lto R
if (a[j-1].key> a[j].key){
a[j-1]↔a[j]; k ← j;
}
R ← k-1;
until (L>R);

Сортировка слиянием
Сортировка слиянием заключается в следующем:
1.Делим последовательность элементов на две части;
2.Сортируем отдельно каждую из частей;
3.Производим слияние отсортированных частей последовательности:
a)при слиянии сравниваем наименьшие элементы и меньший из них отправляем в список вывода;
b)повторяем описанные действия до тех пор, пока не исчерпается одна из частей;
c)все оставшиеся элементы другой части пересылаем в список вывода.

Процедура слияния отсортированных частей последовательности
Алгоритм merge (a, L, Z, R);
i ← L; j ← Z+1; k ← 1;
while (i ≤ Z) &(j ≤R){
if (a[i].key< a[j].key){
c[k]←a[i]; i++; k++;}
else {
c[k]← a[j]; j++; k++;}
}
while (i ≤ Z) {
c[k]←a[i]; i++; k++;}
while (j ≤R){
c[k]←a[j]; j++; k++;}
k ← 0
for i ← L to R {
k++; a[i] ← c[k];}

Сортировка слиянием
Алгоритм merge_sort (L, R);
if (L ≠ R ){
k ← (L+R) div 2;
merge_sort(L, k);
merge_sort(k+1, R);
merge (a, L, k, R);
}

Быстрая сортировка (Хоара)
Суть алгоритма состоит в следующем:
1.Выбрать некоторый элемент х для сравнения (это может быть средний, первый или последний элемент)
2.Используя обмены, выполнить процедуру разделения, суть которой заключается следующем: разбить массив на две части: левую с ключами ≤х и правую с ключами ≥х.

Быстрая сортировка
Данные действия могу быть выполнены, например, следующим алгоритмом:
просматриваем массив слева, пока не встретим элемент а[i]> х
просматриваем массив справа, пока не встретим элемент а[j] < x
меняем местами эти два элемента
продолжаем просмотр обмен до тех пор, пока не буду просмотрены все элементы массива (i> j).
Повторяем процедуру разделения к получившимся двум частям, затем частям частей так далее, пока каждая из частей не будет состоять из одного единственного элемента

Быстрая сортировка
Алгоритм quick_sort (L, R);
x ← a[(L+R) div 2]; i ← L; j ← R;
repeat{
while (a[i].key < x.key) {i++;}
while (a[j].key> x.key) {j--;}
if (i ≤ j) {
a[i] ↔ a[j]; i++; j--;}
} until (i ≥ j)
if (L < j) {quick_sort(L, j);}
if (i < R) {quick_sort(i, R);}

Оценка сложности алгоритма
Процедура разделения n элементов требует Cn операций, так как каждый элемент последовательности необходимо сравнить с выбранным элементом, поэтом рекуррентное уравнение будет иметь вид:
T(n) = Cn+ T(|A1|)+T(|A2|),
где |A1|, |A2| -размеры левой и правой части массива после процедуры разделения.
Если предположить, что разделение в среднем разбивает часть пополам то
Т(n) = Сn+ 2Т(n/2), T(n)= Θ(nlogn).

Оценка сложности алгоритма
Худшим случаем является ситуация, когда в качестве сравниваемого элемента выбирается наибольший из всех элементов рассматриваемой части. В этом случае после процедуры разделения |А1|= n–1, |А2|= 1.
Рекуррентное уравнение будет иметь вид
Т(n) = Сn+ Т(n-1) + Т(1), T(n)=Θ(n2)
Cам Ч. Хоар предполагает, что х надо выбирать случайно, а для небольших выборок останавливаться на медиане.

Пример
Фиксируем элемент x = 7 (средний)

Пример

Пример

Пример

Пример

Порядковые статистики
Задача: дано множество из n чисел. Найти тот его элемент, который будет k-м по счёту, если расположить элементы множества в порядке возрастания.
В англоязычной литературе такой элемент называется k-й порядковой статистикой (order statistic).
Например, минимум (minimum) - это порядковая статистика номер 1, а максимум (maximum) - порядковая статистика номер п.

Порядковые статистики
Медианой (median) называется элемент множества, находящийся (по счёту) посередине между минимумом и максимумом. Точнее говоря, если п нечётно, то медиана - это порядковая статистика номер i = (n + 1)/2, а если n четно, то медиан даже две: с номерами i = n/2 и i = n/2 + 1.
Можно ещё сказать, что, независимо от чётности n, медианы имеют номер i = [(n+1)/2]
В дальнейшем мы будем называть медианой меньшую из двух (если их две).

Порядковые статистики
Пример: 18 24 12 27 19
Медиана =19
Поиск медианы является частным случаем более общей задачи:
нахождение k-го наименьшего элемента из n элементов

Выбор элемента с данным номером
Дано: Множество А из n различных элементов и целое число k, 1 < k < n.
Найти: Элемент х из А, для которого ровно k-1 элементов множества A меньше х.
Эту задачу можно решить за время Θ(n lg n): отсортировать числа, после чего взять k-й элемент в полученном массиве.
Однако, есть и более быстрые алгоритмы.
Рассмотрим алгоритм для нахождения k-го наименьшего элемента из n элементов, предложенный Ч. Хоаром

Выбор элемента с k номером (A1)
Выполняется операция разделения на отрезке [L, R], где первоначально L = 1, R = n , а в качестве разделителя берется x = a[k]. В результате разделения получаются индексы i, j такие, что
a[h] < x, h < i; a[h] > x, h > j; i > j;
a) если j ≤ k ≤ i, то элемент a[k] разделяет массив на две части в нужной пропорции; алгоритм заканчивает вою работу;
b) если i < k, то выбранное значение х было слишком мало, поэтом процесс разделения необходимо выполнить на отрезке [i, R]
c) если k < j , то значение x было слишком велико, поэтому процесс разделения необходимо выполнить на отрезке [L, j]
2. Процесс разделения повторять до тех пор, пока не возникнет ситуация а) - значение x соответствует значению k-oгo наименьшего элемента.

Реализация (A1)
L ← 1; R ← n;
while (L< k) {
x ←A[k];
Разделение a[L] … a[R]
if (i < k) {L ← i;}
if (k < j) {R ← j;}
if (j ≤ k ≤ i) {return x ; break;}
}

Оценка сложности алгоритма (A1)
Если предположить, что разделение в среднем разбивает часть, где находится требуем элемент пополам, то рекуррентное уравнение будет иметь вид T(n) = Cn + T(n/2)
По теореме о решении рекуррентного уравнения трудоемкость алгоритма в среднем есть Θ(n).
Таким образом, получаем явное преимущество по сравнению с прямыми методами, где сначала сортируется все множество, а затем выбирается k-ый элемент.
В худшем случае, когда в качестве разделителя берется максимальный (минимальный элемент) рассматриваемой подпоследовательности, рекуррентное уравнение будет иметь вид
T(n) = Cn + T(n - 1)
трудоемкость алгоритма в этом случае Θ(n2)

Выбор элемента с k номером (A2)
Разбиваем исходную последовательность А на n/5 подпоследовательностей по пять элементов в каждой. В каждой такой подпоследовательности находим медиану. Это потребует C1n операций.
Из найденных на первом шаге медиан строим последовательность M и рекурсивно находим ее медиану x. Так как длина рассматриваемой последовательности M равна n/5, то трудоемкость нахождения медианы для этой последовательности равна T (n/5).
Для полученного элемента x выполним процесс разделения, который потребует C2n операций. В результате вся рассматриваемая последовательность А будет разбита на части: А1 , где элементы не больше x; А2 , где элемент не меньше x. Одна из частей может быть отброшена, причем не сложно показать, что количество элементов каждой из частей не меньше n/4.
Решаем задачу нахождения k-oгo наименьшего элемента оставшихся 3n/4 элементов, что потребует времени T(3n/4).

Оценка сложности алгоритма (A2)
Таким образом, рекуррентное уравнение для описанного выше алгоритма имеет вид
T(n) = C1n + T(n/5) + C2n + T(3n/4)
Решая данное уравнение методом подстановки, при g(n) = 20Cn или методом рекурсивны деревьев, получаем, что трудоемкость приведенного выше алгоритма есть Θ(n).
Если исходную последовательность разбивать на семерки, то рекуррентное уравнение будет иметь вид
T(n) = C3n + T(n/7)+T(3n/4)<(28/3)C3n

Сортировка вычерпыванием
Алгоритм сортировки вычёрпыванием (bucket sort) работает за линейное (среднее) время. Эта сортировка годится не для любых исходных данных: говоря о линейном среднем времени, мы предполагаем, что на вход подаётся последовательность независимых случайных чисел, равномерно распределённых на промежутке [0; 1).
Заметим, что этот алгоритм – детерминированный (не использует генератора случайных чисел); понятие случайности возникает лишь при анализе времени его работы.

Сортировка вычерпыванием
промежуток [0; 1) делится на n равных частей, после чего для чисел из каждой части выделяется свой ящик-черпак (bucket), и n подлежащих сортировке чисел раскладываются по этим ящикам.
Поскольку числа равномерно распределены на отрезке [0;1), следует ожидать, что в каждом ящике их будет немного.
Теперь отсортируем числа в каждом ящике по отдельности и пройдёмся по ящикам в порядке возрастания, выписывая попавшие в каждый из них числа также в порядке возрастания.
Будем считать, что на вход подается n-элементный массив А, причем 0 ≤ А[i] < 1 для всех i.
Используется также вспомогательный массив В[0. .n - 1], состоящий из списков, соответствующих ящикам.

Алгоритм
Алгоритм bucket_sort(A)
n ← length[A]
for i ← 1 to n
{ добавить A[i] к списку B[[nA[i]]] }
for i ← 0 to n-1
{отсортировать список B[i] сортировкой вставками} соединить списки В[0], В[1], …В[n - 1]

Пример

Время работы алгоритма
Операции во всех строках, кроме пятой, требуют (общего) времени Θ(n). Просмотр всех ящиков также занимает время Θ(n). Таким образом, нам остаётся только оценить время сортировки вставками внутри ящиков.
Пусть в ящик B[i] попало ni чисел (ni – случайная величина).
Поскольку сортировка вставками работает за квадратичное время, MO длительности сортировки чисел в ящике номер i есть Θ(М[ni2 ]), а MO суммарного времени сортировки по всех ящиках есть О(n)
Т.е. МО времени работы алгоритма сортировки вычёрпыванием в самом деле линейно зависит от количества чисел.

Время работы алгоритма
Т.к. числа распределены равномерно, а величины всех отрезков равны, вероятность того, что данное число попадет в ящик номер n, равна 1/n.
Это аналогично примеру с шарами и урнами: у нас n шаров-чисел, n урн-ящиков, и вероятность попадания данного шара в данную урну равна р=1/n.
Поэтому числа ni распределены биномиально:
P( ni = k)= Сnkрk (1 – p)n–k ,
М[ni]=nр=1, и
D[ni] = nр(1–р) = 1–1/n.

Лексикографическая сортировка
Пусть S некоторое множество на котором задан
‹– линейный порядок.
Лексикографическим порядком на множестве S называется такое продолжение отношения ‹ на кортежи (списки, слова) элементов из S при котором
(s1 , s2 , …, sp ) ‹ (t1 , t2 , …, tq )
означает выполнение одного из условий:
существует целое j, что sj ‹ tj и для всех i < j справедливо si = ti .
p ≤ q и si = ti при 1 ≤ i ≤ p.

Лексикографическая сортировка
Очевидно, что любое целое число можно считать k-членным кортежем цифр от 0 до n – 1, где n - основание системы счисления, в которой рассматриваются цифры.
Рассмотрим сначала сортировку k-членных кортежей, элементы которых заключены в интервале от ‘a’ до ‘z’.

Сортировка вычёрпыванием
Создадим исходную очередь A из n элементов, в которую занесем все рассматриваемые кортежи длины k.
Организуем количество очередей, равное количеству маленьких латинских букв в алфавите. Для этого используем вспомогательный массив В[‘a’..’z’], состоящий из списков, соответствующих ящикам-черпакам.
Количество итераций равно длине кортежей.
на i -ой итерации идет сортировка по k–i + 1 компоненте кортежей, т.е. некоторый кортеж А[j] удаляется из исходной очереди и добавляется в очередь В[А[j][k–i + 1]].
после выполнения i-ой итерации, в исходной очереди находится последовательность кортежей, полученная в результате “переписывания” (удаления и добавления) элементов всех непустых очередей, начиная с очереди, адрес начала которой находится в переменной В[‘a’], и заканчивая – B[‘z’].

Рекуррентное уравнение для алгоритма
Пусть m — количество организованных очередей, тогда трудоемкость сортировки кортежей по некоторой компоненте есть Θ(n+m),
т.к. количество кортежей – n и их можно распределить по очередям за время O(n); для сцепления m очередей требуется время O(m).
Тогда рекуррентное уравнение будет иметь вид:
T(k) = (n + m) + T(k – 1), T(k) = Θ(k (n + m)).

Алгоритм
Алгоритм lexicographical_sort
k ← length(A[1]);
for c ← ‘a’ to ‘z’
{ B[c].tail ← null; B[c].head ← null; }
for i ← 1 to k {
for j ← 1 to n { B[A[j][k – i + 1]].moveToQueue(A[j]); }
s ← 1;
for c ← ‘a’ to ‘z’
while B[c].head ≠ null
{ A[s] ← B[c].removeFromQueue; s++; }
}

Алгоритм сортировки кортежей разной длины
Сначала сортируемые кортежи располагаются в порядке убывания длины.
Пусть lтах - длина самого длинного кортежа, тогда сортировка вычёрпыванием производится lтах раз.
На начальном этапе в исходную очередь А для сортировки помещаются только кортежи длины lтах и на первом этапе для сортировки используется только компонента lтах .
После этого в исходную очередь А добавляются все кортежи длины lтах – 1, и для сортировки используется только компонента lтах – 1.
На следующих этапах происходит сортировка соответствующей компоненты lтах – 2, … 1, аналогичным образом.

Алгоритм сортировки кортежей разной длины

Оценка сложности

Пример
Дан массив:
Один, Два, Три, Четыре, Пять, Шесть, Семь, Восемь, Девять, Десять
Упорядочиваем по длине:
6 – Четыре, Восемь, Девять, Десять
5 – Шесть
4 – Один, Пять, Семь
3 – Два, Три

1-я итерация
Вспомогательный массив B:
e: Четыре
Ь: Восемь, Девять, Десять

2-я итерация
Вспомогательный массив B:
м: Восемь
р: Четыре
т: Девять, Десять
ь: Шесть

3-я итерация
Вспомогательный массив B:
е: Восемь
н: Один
т: Шесть
ь: Пять, Семь
ы: Четыре
я: Девять, Десять

4-я итерация
Вспомогательный массив B:
а: Два
в: Девять
и: Один, Три
м: Семь
с: Восемь, Шесть, Десять
т: Пять, Четыре

5-я итерация
Вспомогательный массив B:
в: Два
д: Один
е: Девять, Семь, Шесть, Десять, Четыре о: Восемь
р: Три
я: Пять

6-я итерация
Вспомогательный массив B:
в: Восемь
д: Два, Девять, Десять
о: Один
п: Пять
с: Семь
т: Три
ч: Четыре
ш: Шесть

Пирамидальная сортировка
Сортировка пирамидой использует бинарное сортирующее дерево.
Сортирующее дерево — это такое дерево, у которого выполнены условия:
Каждый лист имеет глубину либо d либо d−1, d — максимальная глубина дерева.
Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Пирамидальная сортировка
Этап 1. Выстраиваем элементы массива в виде сортирующего дерева
A[i] ≥ A[2i+1] A[i] ≥ A[2i+2]
0 ≤ i < [n/2]
Этот шаг требует O(n) операций.

Пирамидальная сортировка
Этап 2. Будем удалять элементы из корня по одному за раз и перестраивать дерево, т.е. обменивать A[0] и A[n-1]. В результате обмена A[n-1] будет хранить максимальный элемент массива. Далее уменьшаем размер массива на 1(исключаем последний элемент) и переходим к этапу 1.
Продолжаем до тех пор, пока в дереве не останется 1 элемент.
Этот шаг требует O(nlogn) операций.

Достоинства сортировки
Имеет доказанную оценку худшего случая O(nlogn).
Сортирует на месте, то есть требует всего O(1) дополнительной памяти.

Недостатки сортировки
Неустойчив — для обеспечения устойчивости нужно расширять ключ.
На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
Из-за сложности алгоритма выигрыш получается только на больших n.

Пример

Пример

Пример