Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева

Лабораторная работа 1 Сравнить эффективность методов сортировки массивов Метод прямого выбора и метод сортировки с помощью дерева. Сортировка с помощью прямого выбора Этот прием основан на следующих принципах 1. Выбирается элемент с наименьшим ключом. 2. Он меняется местами с первым элементом ai. 3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока

не останется один, самый большой элемент. Процесс работы этим методом с теми же восемью ключами, что и в табл. 2.1, приведен в табл. 2. Алгоритм формулируется так FORiITO n-1 DO присвоить k индекс наименьшего из ai anJ поменять местами ai и aj end Такой метод его называют прямым выбором в некотором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности

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

Начальные ключи 94 PROCEDURE StraightSfcleclion VAR i,j,k index x item BEGIN FORi1 TO n-1 DO k i x ai FORj i1TO n DO IF aj xTHEN kj X ak END BND аk аi ai x END END StraightSelection Прогр. 3. Сортировка с помощью прямого выбора, Анализ прямого выбора.

Число сравнений ключей С, очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для С имеем с n2 - n2 Число перестановок минимально Mmin3n-l 2.6 в случае изначально упорядоченных ключей и максимально Mmax n24 3n-1 если первоначально ключи располагались в обратном порядке.

Для того чтобы определить Mavg, мы должны рассуждать так. Алгоритм просматривает массив, сравнивая каждый элемент с только что обнаруженной минимальной величиной если он меньше первого, то выполняется некоторое присваивание. Вероятность, что второй элемент окажется меньше первого, равна 12, с этой же вероятностью происходят присваивания минимуму. Вероятность, что третий элемент окажется меньше первых двух, равна 13, а вероятность

для четвертого оказаться наименьшим 14 и т. д. Поэтому полное ожидаемое число пересылок равно Нn 1, где Нn n-е гармоническое число Нn11213 1nНп можно выразить и так Нп In ng 12n 112n2 где g 0.577216 константа Эйлера. Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением Fi-ln igl

Среднее число пересылок Mavg в сортировке с выбором есть сумма Fi с i от 1 до n MavgnglSi 1 i n lni Вновь аппроксимируя эту сумму дискретных членов интегралом Integral 1 п ln x dx x ln x 1 n ln п n I получаем, наконец, приблизительное значение Mavg nln n g Отсюда можно сделать заключение, что, как правило, алгоритм с прямым выбором предпочтительнее строгого включения. Однако, если ключи в начале упорядочены или почти упорядочены, прямое включение

будет оставаться несколько более быстрым. 2. Сортировка с помощью дерева Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n 1 элементов и т. д. Обнаружение наименьшего среди п элементов требует это очевидно n 1 сравнения, среди n 1 уже нужно n 2 сравнений и т. д. Сумма первых n 1 целых равна 12n2 n. Как же в таком случае можно усовершенствовать упомянутый метод

сортировки Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n2 сравнений, можно определить в каждой паре ключей меньший. С помощью n4 сравнений меньший из пары уже выбранных меньших и т. д. Проделав n 1 сравнений, мы можем построить дерево выбора вроде представленного на рис.

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

только дырки, и процесс сортировки заканчивается. Обратите внимание на каждом из n шагов выбора требуется только log n сравнений. Поэтому на весь процесс понадобится порядка nlog n элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение не только прямого метода, требующего п2 шагов, но и даже метода Шелла, где нужно п1.2 шага. Естественно, сохранение дополнительной информации делает задачу более изощренной, поэтому в сортировке

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

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

Прим. перев. изобретенном Д. Уилльямсом 2.14, где было получено, очевидно, существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей hi hL1, , hr, такая, что Если любое двоичное дерево рассматривать как массив по схеме на рис. 2.6, то можно говорить, что деревья сортировок на рис. 2.7 и 2.8 суть пирамиды, а элемент h1, в частности, их наименьший элемент himinhi, h2, hn.

Предположим, есть некоторая пирамида с заданными элементами hL1, hR для некоторых значений L и R и нужно добавить новый элемент х, образуя расширенную пирамиду hi . li R. Возьмем, например, в качестве исходной пирамиду hi, hr, показанную на рис. 2.7, и добавим к ней слева элемент h144 Это несколько противоречит утверждению, что lui hr пирамида, но надеемся, сам читатель разберется, Что хотел сказать автор.

Прим. перев. Новая пирамида получается так сначала х ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значение 44 сначала меняется местами с 06, затем с 12 ц в результате образуется дерево, представленное на рис. 2.8. Теперь мы сформулируем этот сдвигающий алгоритм так i, j пара индексов, фиксирующих элементы,

меняющиеся на каждом шаге местами. Читателю остается лишь убедиться самому, что предложенный метод сдвигов действительно сохраняет неизменным условия 2.13, определяющие пирамиду. Р. Флойдом был предложен некий лаконичный способ построения пирамиды на том же месте. Его процедура сдвига представлена как прогр. 2.7. Здесь hi . hn некий массив, причем Ьщ hn пп nDIV21 уже образуют пирамиду, поскольку индексов i, j, удовлетворяющих

отношениям j 2i или j 2i1, просто не существует. Эти элементы образуют как бы нижний слой соответствующего двоичного дерева см. рис. 2.6, для них никакой PROCEDURE siftL, R index VAR i, j index x item BEGIN i L J 2L x aL IF j R aJl aj THEN jjl END WHILE j Raj x DO ai aj ij i 2j IFj Raj1 aj THEN jj1 END END END sift Прогр. 2.7. Sift. упорядоченности не требуется.

Теперь пирамида расширяется влево каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Табл. 2.6 иллюстрирует весь этот процесс, а получающаяся пирамида показана на рис. 2.6. Следовательно, процесс формирования пирамиды из п элементов hi hn на том же самом месте описывается так L n DIV 2 1 WHILE L 1 DO L L 1 siftL, n END Для того чтобы получить не только частичную, но и полную упорядоченность среди элементов, нужно проделать n сдвигающих шагов, причем после каждого шага на вершину

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

Таблица 2.6, Построение пирамиды Таблица 2.7. Пример процесса сортировки с помощью Heapsort чае n 1 шагов. Сам процесс описывается с помощью процедуры sift прогр. 2.7 таким образом Rn WHILE R 1 DO х аl al aR aR x RR-l siftl,R END Пример из табл. 2.7 показывает, что получающийся порядок фактически является обратным. Однако это можно легко исправить, изменив направление упорядочивающего отношения в процедуре sift.

В конце концов получаем процедуру Heapsort прогр. 2.8, PROCEDURE HeapSort VAR L, R index х item PROCHDURE siftL, R index VAR i,jindex x item BEGIN i L j 2L x aL IFj R aj aj1 THEN j jl END WHILEj Rx ajDO aiaj i j j2j IFJ Rai ajl THENjj1 END END END sift BEGIN LnDIV2lRn

WHILE L 1 DO L L-l siftL, R END WHILER 1 DO x al al aR aR x R R-l siflL, R END END HeapSort Прогр. 2.8. HeapsorL Анализ Heapsort. На первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. И действительно, процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа

элементов. Для больших же n Heapsort очень эффективна чем больше п, тем лучше она работает. Она даже становится сравнимой с сортировкой Шелла. В худшем случае нужно п2 сдвигающих шагов, они сдвигают элементы на log n2, log п2 1, logn l позиций логарифм по основанию 2 обрубается до следующего меньшего целого. Следовательно, фаза сортировки требует n 1 сдвигов с самое большое logn 1, logn 2, 1 перемещениями.

Кроме того, нужно еще n 1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев Heap-sort потребует nlog n шагов. Великолепная производительность в таких плохих случаях одно из привлекательных свойств Heapsort. Совсем не ясно, когда следует ожидать наихудшей или наилучшей производительности. Но вообще-то кажется, что Heapsort любит начальные последовательности, в которых элементы более или

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