В этой
теме продолжаем изучать методы сортировок массивов, которые получены усовершенствованием
простых методов.
В 1959 г. Д.Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. После первого прохода элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на две позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка. Например: Дан массив, состоящий из элементов: 44 55 12 42 94 18 06 67После четверной сортировки получаем: 44 18 06 42 94 55 12 67Т.е. элементы, отстоящие на 4 позиции друг от друга сравниваются и меняются местами в случае необходимости (44<94, 55>18 значит меняем местами, 12>06 тоже меняем местами, 42<67). После двойной сортировки получаем: 06 18 12 42 44 55 94 67Теперь сравниваем элементы, отстоящие на 2 позиции (44>06 - меняем, 94>12 - меняем, 44>12 - меняем и т.д.) После одинарной сортировки получаем: 06 12 18 42 44 55 67 94На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок. Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояния обозначаются соответственно h1,h2,...,ht, для них выполняются условия ht=1, hi+1<hiКаждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров. Ясно, что каждая из сортировок нуждается в постановке своего собственного барьера и программу для определения его местоположения необходимо делать насколько возможно простой. Поэтому приходится расширять массив не только на одну-единственную компоненту a0, а на h1 компонент. Анализ этого алгоритма поставил несколько проблем. Не известно, какие расстояния дают наилучшие результаты. Д.Кнут в работе ╚Искусство программирования для ЭВМ╩ показывает, что имеет смысл использовать такую последовательность ( записана в обратном порядке): 1, 4, 13, 40, 121, ... или 1, 3, 7, 15, 31, ...Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n1.2. Метод сортировки
с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа
среди n элементов, среди оставшихся n-1 элементов и т.д. Обнаружение наименьшего
среди n элементов требует - это очевидно - n-1 сравнения, среди n-1 нужно
n-2 сравнений и т.д. Сумма первых n-1 целых равна 1/2(n2-n).
Как же в таком случае можно усовершенствовать упомянутый метод сортировки?
Этого можно добиться, только оставляя после каждого прохода больше информации,
чем просто идентификация единственного минимального элемента. Например,
сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С
помощью n/4 сравнений - меньший из пары уже выбранных меньших и т.д. Проделав
n-1 сравнений, мы можем построить дерево выбора и идентифицировать его
корень как нужный нам наименьший ключ.
Повторяющиеся выборы среди двух ключей. Второй этап
сортировки - спуск вдоль пути, отмеченного наименьшим элементом, и исключение
его из дерева путем замены либо на пустой элемент (дырку) в самом низу,
либо на элемент из соседней ветви в промежуточных вершинах.
12 ?Выбор наименьшего ключа.
12
12
18
44 12 18 67 44 55 12 42 94 18 ? 67 Заполнение дырок. Элемент, передвинувшийся в корень дерева, вновь будет наименьшим (теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (т.е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внимание - на каждом из n шагов выбора требуется только n·logn элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение. Естественно, сохранение дополнительной информации делает задачу более изощренной, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Наша следующая задача - найти приемы эффективной организации этой информации. Это удалось добиться в методе Heapsort, изобретенном Д.Уилльямсом. Пирамида определяется
как последовательность ключей hL, hL+1,...,hR,
такая, что
h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 h12 h13 h14 h15 Предположим,
есть некоторая пирамида с заданными элементами hL+1,...,hR
для некоторых значений L и R и нужно добавить новый элемент x, образуя
расширенную пирамиду hL,...,hR. Возьмем, например,
в качестве исходной пирамиду h1,...,h7
42
06
55 94 18 12 и добавим к ней слева элемент h1=44. Новая пирамида получается так: сначала x ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значение 44 сначала меняется местами с 06, затем с 12 и в результате образуется дерево
06
Р.Флойдом был
предложен способ построения пирамиды ╚на том же месте╩. Его процедура сдвига
представлена в программе процедурой sift.
L:=(n div 2) +1;Для того чтобы получить не только частичную, но и полную упорядоченность среди элементов, нужно проделать n сдвигающих шагов, причем после каждого шага на вершину дерева выталкивается очередной (наименьший) элемент. type mass=array[1..100] of integer; На первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. Процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для больших же n Heapsort очень эффективна; чем больше n, тем лучше она работает. В худшем случае
нужно n/2 сдвигающих шагов, они сдвигают элементы на log2(n/2),
log2(n/2-1),...,log2(n-1) позиций (логарифм ╚обрубается╩
до следующего меньшего целого). Следовательно, фаза сортировки требует
n-1 сдвигов с самое большое log2(n-1), log2(n-2),...,1
перемещениями. Кроме того, нужно еще n-1 перемещений для просачивания сдвинутого
элемента на некоторое расстояние вправо. Эти соображения показывают, что
даже в самом плохом из возможных случаев Heapsort потребует n*log2n
шагов.
Теперь коснемся третьего улучшенного метода, основанного на обмене. Улучшение метода, основанного на обмене, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Изобретатель Ч.Хоар назвал этот метод быстрой сортировкой (Quicksort). В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Давайте, попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент ai>x, затем будем просматривать массив справа, пока не встретим aj<x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую с ключами больше (или равными) x. Если взять в качестве x для сравнения средний ключ 42, то в массиве ключей 44 55 12 42 94 06 18 67для разделения понадобятся два обмена: 18≈44 и 6≈55. Получаем 18 06 12 42 94 55 44 67последние значения индексов таковы: i=5, а j=3. Ключи a1...ai-1 меньше или равны ключу x=42, а ключи aj+1...an больше или равны x. Следовательно, существует две части, а именно Ak:1<= k < i:ak <= x Ak: j< k <= n:x <= ak Наша цель - не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям частей, и так до тех пор пока каждая из частей не будет состоять из одного-единственного элемента. Суть итеративного решения заключается во введении списка требуемых разделений, т.е. разделений, которые необходимо провести. На каждом этапе возникают две задачи по разделению. И только к одной из них мы можем непосредственно сразу приступить в очередной итерации, другая же заносится в упомянутый список. При этом, конечно, существенно, что требования из списка выполняются несколько специфическим образом, а именно в обратном порядке. Следовательно, первое из перечисленных требований выполняется последним, и наоборот. В приводимой не рекурсивной версии Quicksort каждое требование задается просто левым и правым индексами - это границы части, требующей дальнейшего разделения. Вводим индекс s, указывающий на самую последнюю строку в стеке. О том, как выбрать подходящий размер стека m, речь пойдет при анализе Quicksort. const m=4; n=20; Для исследования производительности Quicksort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. Следовательно, при этом выполняется точно n сравнений. Число же обменов можно определить из следующих вероятностных соображений. При заданной границе значений x ожидаемое число операций обмена равно числу элементов в левой части разделяемой последовательности, т.е. n-1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, если этот элемент перед этим находился в правой части. Вероятность этого равна (n-(x-1))/n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x. m = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/nПредставим себе, что нам всегда удается выбрать в качестве границы медиану, в этом случае каждый процесс разделения расщепляет массив на две половины и для сортировки требуется всего log2n проходов. В результате общее число сравнений равно n*log2n, а общее число обменов - n*log2(n)/6. Средняя производительность Quicksort при случайном выборе границы отличается от упомянутого оптимального варианта лишь коэффициентом 2*ln(2). Как бы то ни было, но Quicksort присущи и некоторые недостатки. Главный из них - недостаточно высокая производительность при небольших n. Литература 1. Н.Вирт. Алгоритмы и структуры данных.Упражнения 1. Дан массив целых чисел a[1..n]. Отсортировать его методом Шелла. |