АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
9.4. Краткая теория
Все прямые методы сортировки фактически передвигают каждый элемент на всяком элементарном шаге на одну позицию. По этой причине они требуют порядка O(n2) таких шагов. Отсюда следует, что в основу любых улучшений должен быть положен принцип перемещения элементов на каждом шаге на возможно большие расстояния.
Метод Шелла.
Метод Шелла является улучшением метода сортировки с помощью прямого включения и основан на сортировке посредством включением с уменшающимися расстояниями. Сначала отдельно группируются и сортируются методом прямых включений элементы, отстоящие друг от друга на некотором расстоянии h1, затем на расстоянии h2 < h1 и так далее, последнее расстояние должно быть равно единице. Таким образом, если для сортировки будет использовано t расстояний, то ht = 1, hi+1< hi. Желетельно, чтобы расстояния обеспечивали бы взаимодействие различных цепочек как можно чаще.
Рассмотрим процесс сортировки последовательности из 8 целых чисел с начальным шагом h1 = 4, вторым шагом h2 = 2 и последним шагом h3 = 1.
Последовательность чисел: 44, 55, 12, 42, 94, 18, 6, 67.
На рисунке ниже представлена иллюстрация сортировки методом Шелла данной последовательности.
Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.
На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако, на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок. Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает; также очевидно, что расстояния в группах можно уменьшать по разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.
Приводимый ниже в псевдокоде алгоритм не ориентирован на некую определенную последовательность расстояний и использует метод прямой вставки с условным переходом. Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while , то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера. При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0..N ] до [-h1..N ], что усложнит написание программы.
Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, … то есть: hm=2hm-1+1, а количество шагов
t = (log 2 n) - 1.
При такой организации алгоритма его эффективность имеет порядок O ( n1,5 )
Другим улучшенным методом сортировки является так называемая быстрая сортировка (QuickSort), которая считается сортировкой разделением и носит также назавание быстрая сортировка Хоара.
Quiсksort - метод быстрой сортировки
Быстрая сортировка является усовершенствованием метода, основанного на обмене. В основу данной сортировки положен метод разделения ключей по отношению к выбранному. Он заключается в следующем. Выбираем наугад какой-либо элемент x исходного массива. Будем проматривать массив слева до тех пор, пока не встретим ai > x, затем будем просматривать массив справа, пока не встретим aj < x. Поменяем местами эти два элемента и продолжим процесс просмотра до тех пор, пока оба просмотра не встретятся. В результате исходный массив окажется разбитым на две части, левая часть будет содержать элементы меньшие или равные x, а правая часть – элементы большие x. Применив эту процедуру разделения к левой и правой частям массива от точки встречи, получим четыре части и так далее, пока в каждой части окажется только один элемент. Остается решить вопрос, каким образом выбирать элемент x для разделения. Если при равновероятном распределении элементов массива в качестве разделения каждый раз выбирать медиану, то общее число сравнений будет n*log2n, а общее число обменов – (n*log2n)/6. При случайном выборе границы средние затраты увеличатся всего лишь в n*ln2 раза. В крайне неблагоприятном случае, когда каждый раз для разделения выбирается наибольший обрабатываемый элемент массива, производительность процедуры будет наихудшая. Обычно в процедурах бысторой сортировки в качестве границы выбирают средний элемент, при этом получаются хорошие показатели производительности.
Нижеприведенный рисунок иллюстрирует процесс обменной сортировки
Слева от 6 располагают все ключи, которые меньше 6 , а справа - которые больше или равны 6.
Из всех существующих методов сортировки QuickSort самый эффективный. Его эффективность имеет порядок
О (n log2 n) .