Презентация на тему Улучшенные сортировки

Шелл: для алгоритмов сортировки, перемещающих в последовательности запись вправо

или влево только на одну позицию, среднее время работы будет в лучшем случае пропорционально N2.

Хотелось бы, чтобы записи перемещались «большими скачками, а не короткими шажками».

Д. Шелл предложил в 1959 г. метод, названный сортировкой с убывающим шагом.

подпоследовательности элементы, отстоящие друг от друга на четыре позиции:





Полученные

4 последовательности отсортируем на месте независимо друг от друга методом простых включений.

Этот процесс называется 4-сортировкой.

последовательность:
_________________________________

| | | |
40 14 2 38 90 51 8 63
|__________|__________|__________|

На следующем шаге элементы, отстоящие друг от друга на две позиции, объединяются в подпоследовательности и сортируются простыми вставками независимо друг от друга.
Этот процесс называется 2-сортировкой.
После 2-сортировки получим последовательность:
2 14 8 38 40 51 90 63
Ее сортируют методом простых вставок.
К последнему шагу элементы довольно хорошо упорядочены,
поэтому требуется мало перемещений.
Данный процесс называется 1-сортировкой.

можно использовать любую убывающую последовательность шагов
ht, ht-1, ...,

h1
Чтобы выбрать некоторую хорошую последовательность шагов сортировки, нужно проанализировать время работы как функцию от этих шагов.
До сих пор не удалось найти наилучшую возможную последовательность шагов ht, ht-1, ..., h1 для больших N.
Выявлен примечательный факт, что элементы последовательностей приращений не должны быть кратны друг другу.
Это позволяет на каждом проходе сортировки перемешивать цепочки, которые ранее никак не взаимодействовали.
Желательно, чтобы взаимодействие между разными цепочками происходило как можно чаще.
Кнут:
..., 121, 40, 13, 4, 1, где hk+1= 3  hk + 1, h1 = 1
..., 31, 15, 7, 3, 1, где hk+1 = 2 hk + 1, h1 = 1

i), то она остается k-отсортированной.
→ C каждым следующим шагом

сортировки с убывающим приращением количество отсортированных элементов в последовательности возрастает.
Для последовательности шагов 2k + 1, ..., 9, 5, 3, 1
количество пересылок пропорционально N1.27,
для последовательности 2k – 1, ..., 15, 7, 3, 1 — N1.26,
для последовательности (3k – 1)/2, ..., 40, 13, 4, 1 — N1.25

Общая оценка: величина порядка N3/2

первого элемента последовательности
// h – величина шага
начало процедуры

// Пусть i – номер первого элемента в несортированной части массива
i := b + h;
пока i  N выполнять
x:= A[i];
j := i – h;
пока j  b и A[j]>x выполнять
// Все элементы из отсортированной части, большие
// x, сдвинуть на величину шага h вправо,
A[j+h] := A[j];
j := j – h;
конец пока
// Элемент x поставить на свое место по порядку:
A[j+h] := x;
i := i + h;
конец пока
конец процедуры

пока h < N/3 выполнять
h :=

3*h + 1;
конец пока
// Сортировка:
пока h  1 выполнять
цикл по i от 1 до h с шагом 1 выполнять
Вставка (i, h);
конец цикла
h := (h – 1) / 3;
конец пока

шаге выполняется линейный поиск минимального элемента. Линейная сложность этого

поиска делает сложность всей сортировки квадратичной.
Возможно ли найти минимальный элемент за время лучшее линейного?
Оказывается, что это возможно, если использовать на каждом следующем шаге информацию о взаимных отношениях элементов, накопленную на предыдущих шагах.
Идея бинарного выбора может быть эффективно применена, если организовать входные данные в виде так называемой пирамиды (или сбалансированного бинарного дерева поиска) и поддерживать их в этом виде в процессе сортировки.
Метод сортировки с использованием такой пирамиды был предложен Р. У. Флойдом в 1964 г. под названием «Heap sort» — пирамидальной сортировки или сортировки кучей.

hi образует пирамиду в этой последовательности,
если выполнены следующие условия:

если 2  i ≤ n, то hi ≥ h2i и h2i образует пирамиду;
если 2  i + 1 ≤ n, то hi ≥ h2i+1 и h2i+1 образует пирамиду.

Элементы hn/2+1, ..., hn всегда образуют тривиальные пирамиды, поскольку для них приведенные условия имеют ложные посылки.
Если элемент h1 образует пирамиду, то и каждый элемент последовательности образует пирамиду.
В этом случае будем говорить, что вся последовательность является полной пирамидой.

в виде корневого бинарного дерева, в котором элементы h2i

и h2i+1 являются сыновьями элемента hi.
Элемент в любом узле численно не меньше всех своих потомков, а вершина полной пирамиды h1 содержит максимальный элемент всей последовательности.

h1

h14

h13

h12

h11

h10

h9

h15

h8

h7

h6

h5

h4

h3

h2

полной пирамиде не равно 2k – 1, самый нижний

уровень дерева будет неполным: недостающих сыновей можно достроить, добавив в пирамиду несколько заключительных «минимальных» элементов «0», не нарушающих условия пирамиды.
Последовательность, упорядоченная по убыванию, является полной пирамидой.
Например, последовательность из 12 элементов
12, 11, 7, 8, 10, 6, 3, 2, 1, 5, 9, 4
является полной пирамидой с вершиной 12.

12

0

0

4

9

5

1

0

2

3

6

10

8

7

11

последовательность перестраивается в пирамиду.
Сортировка: входная и готовая последовательности хранятся

в одном массиве, причем готовая последовательность формируется в хвосте массива, а входная остается в начале массива.

Основой реализации метода является следующая процедура просеивания.
Пусть в последовательности h1, ..., hn элементы hi+1, ..., hn уже образуют пирамиды.
Требуется перестроить последовательность так, чтобы пирамиду образовывал элемент hi.
На каждой итерации цикла наибольший из трех элементов hi, h2i и h2i+1 путем обмена оказывается в корне текущего поддерева, что обеспечивает истинность условий пирамиды в этом корне.
Если при этом изменяется корень левого или правого поддерева, то просеивание продолжается для него.

a1 a2

a3 a4 a5 a6 a7 a8 a9 a10
Шаг 1, i=5: 52 81 42 23 11 76 91 63 37 20
Шаг 2, i=4 : 52 81 42 23 20 76 91 63 37 11
Шаг 3, i=3 : 52 81 42 63 20 76 91 23 37 11
Шаг 4, i=2 : 52 81 91 63 20 76 42 23 37 11
Шаг 5, i=1 : 52 81 91 63 20 76 42 23 37 11
Выход: 91 81 76 63 20 52 42 23 37 11

е. максимальный элемент пирамиды, переносится в начало готовой последовательности

путем обмена с последним элементом пирамиды, занимающим его место.
Затем остаток входной последовательности вновь перестраивается в пирамиду, обеспечивая корректность следующего шага.
В начале i-го шага элементы a1, .., ai, по предположению, хранят входную последовательность как пирамиду, а ai+1, .., aN – упорядоченную по возрастанию готовую последовательность (изначально пустую).
На i-м шаге текущий максимальный элемент пирамиды а1 обменивается с аi, становясь началом новой готовой последовательности, где он будет новым минимальным элементом. Входная последовательность (пирамида) при этом претерпевает два изменения:
— она теряет последний элемент, что не нарушает условий пирамиды ни в одном узле;
— ее первый элемент становится произвольным, что может нарушать условие пирамиды только в первом узле.

..., ai-1
условия пирамиды выполнены для всех элементов, кроме

первого.

Применение процедуры просеивания к a1 восстанавливает полную пирамиду в a1, ..., ai-1, что обеспечивает условия осуществимости следующего шага.

элемента, который нужно просеять

// n – номер последнего элемента массива
начало процедуры
пока 2*i <= n
r := 2*i;
если (r+1  n) и (A[r] < A[r+1])
то r := r + 1;
// i-тый элемент массива ставится на то место,
// где он удовлетворяет свойству пирамиды:
// A[i]  max(A[2*i], A[2*i + 1])
если A[i] < A[r]
то начало
Обмен (i, r);
i := r;
конец
иначе выход из процедуры;
конец пока
конец процедуры

/ 2;
пока i  1 выполнять
Просеивание (i, N);
i

:= i – 1;
конец пока
Шаг 2. Сортировка на пирамиде:
i := N;
пока i > 1 выполнять
Обмен (1, i);
i := i – 1;
Просеивание (1, i);
конец пока
конец основной программы

высоты пирамиды.

Высота полного бинарного дерева из N узлов,

каковым является пирамида, равна [log2 N].
Просеивание имеет логарифмическую сложность.

Итоговая сложность пирамидальной сортировки ~N  log2 N.

Наилучший случай – обратное упорядочение входной последовательности.

Хоар
Это метод сортировки, при котором обмениваются местами пары

несоседних элементов, а задача сортировки последовательности рекурсивно сводится к задачам сортировки ее меньших частей.
Допустим сначала, что мы уже переупорядочили некоторым образом элементы входной последовательности, после чего оказалось возможным разделить ее на две непустые части по границе некоторого индекса т:
левую (индексы 1...т) и
правую (индексы т+1...N);
причем значения всех элементов левой части не превосходят значений всех элементов правой части:
 i, j: 1  i  m и m < j  N выполнено: аi  aj. (*)
Индекс т назовем медианой.

левую часть, не затрагивая элементов правой части, а затем

отдельно правую, не трогая левой.
При этом обмениваться могут только пары элементов, находящиеся в одной части, поэтому никакой обмен не нарушает свойство (*).
Значит, оно будет верно и для результирующей последовательности, которая в силу этого оказывается упорядоченной в целом.
СортировкаРазделением (l, r)
/* l, r – границы сортируемой подпоследовательности */
/* Разделение */
привести подпоследовательность аl,…, аr к условию (*)
и определить медиану m;
/* Рекурсивный спуск */
если l < m то // части длины 0 и 1 не сортируем
СортировкаРазделением (l, m);
если m + 1 < r то // части длины 0 и 1 не сортируем
СортировкаРазделением (m + 1, r);
конец

подзадачи мы приходим к тривиальным подзадачам: сортировке последовательностей длины

0 и 1.
Не приходится ничего делать и для слияния решений подзадач в решение исходной задачи во время возврата из рекурсии: упорядоченные последовательности образуются сами собой по мере упорядочения их частей.
Где же тогда фактически выполняется сортировка?
- На фазе разделения, иллюстрируя, как хорошая подготовка условий для решения зачастую уже и дает решение!
В качестве критерия разделения нам понадобится так называемый пилотируемый элемент х.
В классической версии алгоритма в качестве x выбирается произвольный элемент сортируемой последовательности: первый, последний, расположенный в середине или иначе.
Влияние его выбора на эффективность алгоритма мы обсудим ниже.

последовательности все элементы аi  х, а в правой

— все элементы aj  x.
Условие (*) при этом будет выполнено даже при возможном наличии одинаковых элементов x в обеих частях.
Введем два бегущих индекса-указателя i и j, которые делят разделяемую подпоследовательность на три участка:
левый (al ... ai-1),
правый (aj+1 ... ar),
средний (ai ... aj).

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

ai < х цикл /* проверка i < r

не нужна: х где-то есть */
i := i + 1; /* в конце ai  х */
конец цикла;
пока х < aj цикл /* проверка j > i не нужна: х есть */
j := j – 1; /* в конце aj  х */
конец цикла;
если i ≤ j то /* если i = j, a[i = j] = x, нужен сдвиг индексов
для выхода из цикла */
обменять ai и aj ; /* теперь ai  х  aj */
i := i + 1; /*на случай ai = х : добавить в левую часть */
j := j – 1;/* на случай aj = х : добавить в правую часть */
пока i < j;

в левую или правую элементы, строго меньшие или большие

х, которые могут быть добавлены в эти части без перестановки.

После их выполнения процесс разделения либо заканчивается (если i  j), либо пара ai и aj образует инверсию.

В последнем случае их следует обменять и включить в левую и правую части.

Вот здесь и происходят упорядочивающие обмены с уменьшением числа инверсий в последовательности!

границы l...r, строго говоря, необходима, но фактически не нужна:

на первом проходе выход за границы немозможен, так как в массиве есть сам элемент х и оба цикла остановятся на нем.

В конце же первого прохода происходит обмен элементов и обе части становятся не пусты, что гарантирует остановку циклов по встречным индексам в пределах интервала l...r и на следующих проходах.

надо определить медиану.

Определенные границы левой части – l...i

– 1,
правой – j + 1...r, однако интервал j + 1...i – 1 может быть не
вырожден и заполнен элементами х (почему?).

Эти элементы останутся на своих местах в процессе
сортировки (почему?), поэтому их можно исключить из
левой и правой частей.

Окончательно границами левой части можно считать l...j,
а правой – i...r.

8 38 89 1 15

63
Начало: i x j
Первый проход:i j Сближение
Обмен
15 51 8 38 89 1 40 63
Второй проход: i j Сближение
Обмен
i j
15 1 8 38 89 51 40 63
Третий проход: i j Сближение ij Обмен
15 1 8 38 89 51 40 63
Четвертый проход: j i Сближение

сравнений.

Число обменов?
Пусть после разделения х будет занимать

в массиве позицию k.

Число требующихся обменов равно числу элементов в левой части массива (k - 1), умноженному на вероятность того, что элемент нужно обменять.

Элемент обменивается, если он не меньше, чем х.
Вероятность этого равна (N - (k - 1))/N.

эту сумму на N, в результате получим ожидаемое число

обменов:



Ожидаемое число обменов равно приблизительно N/6.
В лучшем случае каждое разделение разбивает массив на две равные части, а число проходов, необходимых для сортировки, равно log2 N.
Тогда общее число сравнений равно N log2 N.