Programmirovanie_i_osnovyi_algo

при i-oM просеивании составляет самое большее /, а самое меньшее - 1. Число М, пересылок (присваиваний) элементов при /-ом

просеивании равно

(С,-1) + 3 = С,+2

Это объясняется тем, что тело цикла while выполняется на один раз меньше, чем число проверок условия повтора цикла. Три других пересылки при /-ом просеивании есть:

Л^сРЕд=(Л^м1м+^мАх)/2 = (3-(^/2е-2) + С9/2еч-5)-(^/^^-2)/2)/2.

C^^iM и Л/^д,^, имеют место, если элементы массива с самого на­ чала упорядочены, а С^^дх и Л/^АХ встречаются, если элементы масси­ ва расположены в обратном порядке.

15.4. Сортировка массива простым обменом (метод "пузырька")

Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Пример сортировки массива методом "пу­ зырька" приведен на рис. 66.

Очевидно, что в наихудшем случае, когда минимальное значе­ ние ключа элемента имеется у самого правого элемента, число про­ смотров равно size-\.

Прототип функции сортировки массива простым обменом, ее определение и пример вызова даны в примере, приведенном в подразд. 15.2. Внимательно изучите их.

250

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

15.5. Выводы по простым методам сортировки

1. в простых методах сортировки массивов время сортировки пропорционально size^.

2. Более точные оценки производительности простых методов

251

сортировки массивов показывают, что наиболее быстрой является

сортировка вставками, а наиболее медленной - сортировка обме­ ном.

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

4.Наряду с простыми алгоритмами сортировки массивов су­ ществуют сложные алгоритмы сортировки, обеспечивающие время сортировки, пропорциональное не size^, а size-logjisize). При больших значениях size они обеспечивают существенный выигрыш. К их рас­ смотрению мы и переходим.

15.6.Сортировка массива сложным выбором

(с помощью двоичного дерева)

Данная сортировка, по сравнению с сортировкой простым вы­ бором, обладает большим быстродействием за счет сокращения за­ трат времени на выбор максимального элемента.

/ . Идея алгоритма. Исходное состояние двоичного дерева (ключи исходного массива структур агг с числом элементов size) показано на рис. 67.

а Вначале двоичное дерево подготавливаем таким образом, чтобы элемент массива с максимальным значением ключа (94) находился в корне дерева.

• Выбираем элемент с максимальным значением ключа, меня­ ем его местами с последним элементом массива и затем восстанав­ ливаем двоичное дерево (рис. 68). Вновь найденный элемент с мак­ симальным значением ключа (67), который после восстановления двоичного дерева оказывается опять в его корне, меняется местами с предпоследним элементом массива и т.д. (всего size-\ раз).

Таким образом, получаем общее число сравнений

С= {size -1) • log 2 {size)

иКакие в связи с этим возникают проблемы?

Как построить двоичное дерево (пирамиду) без дополнитель­ ных затрат памяти с тем, чтобы обеспечить сортировку "на месте", т.е. обойтись в дереве size вершинами вместо (5/z^*2-l) вершин?

Как организовать дерево в самом начале работы?

252

Всего ( 2*size-1 ) вершин

94

Рис. 67. Исходное состояние двоичного дерева

Вместо выбранного элемента с максимальным значением ключа (94) появились «дырки»

На восстановление двоичного дерева потребовалось 1од2( size ) сравнений претендентов на заполнение «дырок»: 1, 2, 3

Рис. 68. Двоичное дерево после первой замены и восстановления

2. Построение пирамиды (двоичного дерева) **на месте'* и ее начальное заполнение,

2.1. Представление двоичного дерева из size элементов в од­ номерном массиве из size элементов. Из вершины двоичного дерева, в обш;ем случае, идут две дуги вниз (см. выше рис. 57), отсюда тер­ мин - двоичное дерево.

В двоичном дереве могут встретиться следующие случаи:

• у 1 > size - вершина / есть лист дерева;

•j \ ~ size - нет7*2;

•yi < size - есть у 1 иу2.

Таким образом, для представления массива из size элементов

253

требуется дерево с size вершин. У каждой вершины может быть О, 1 или 2 дуги вниз (О -лист, 1 или 2 дуги вниз - промежуточная верши­ на или корень).

Для рассмотренного выше примера мы получаем следующее

В отличие от первого дерева из (2*^/ze-l)=15 вершин ключ 94 встречается один, а не четыре раза. Ключ 55 встречается один, а не три раза и т.д. Выигрыш налицо!

2.2. Как подготовить дерево в самом начале, когда в массиве царит беспорядок?

В первую очередь рассмотрим поддеревья-листья 5, 6, 7, 8 (нижний слой на рис. 69). Каждое из поддеревьев-листьев из одной вершины и, следовательно, они упорядочены.

Вершина с максимальным номером, у которой есть следующие снизу вершины, имеет номер size/2 (при size=^ такая вершина имеет номер 4). Поэтому подготовку дерева надо начинать с вершины с

254

Size/2=4

В корне соответствующего поддерева образуем «дыру» путем копирования соответствующего корню элемента в сору. Ищем подходящее место для вставки сору и помещаем в него сору.

Рис. 72. Подготовка двоичного дерева для вершины 2

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

{size -1) • log2 {size).

255

3.функция просеивания

3.1.Идея функции (см. рис. 57)

42

Рис. 73. Подготовка двоичного дерева для вершины 1

256

примеры вызовов содержатся в примере программы, приведенном выше в подразд. 15.2. Обратите внимание на то, что функция про­ сеивания используется только для внутренних целей и, таким обра­ зом, не является интерфейсной (вызывается из функции сортировки сложным выбором). Функция же сортировки сложным выбором, на­ против, является интерфейсной. Это означает, что она вызывается

{logjisize))/2 раз, содержит одну пересылку в теле цикла и две пере­ сылки за пределами цикла. В функции TreeSort сортировки сложным

нем 2'(\og2(size))/2 = \og2(size) сравнений. Поэтому общее число сравне­ ний

С = (log2 (size))' (size -1) + (log2 (size)) • size 12,

что также пропорционально size*\og2(^ize).

15.7. Сложная сортировка вставками (сортировка Шелла)

Идея алгоритма,

1.Используется несколько проходов.

2.На первом проходе отдельно группируются и сортируются

257

Текст функции. Прототип функции ShellSort сложной сорти­ ровки вставками, ее определение и пример вызова приведены выше в программе, текст которой дан подразд. 15.2.

Рис. 74. Иллюстрирующий пример для сортировки Шелла

Вместе с тем выявлено, что лучшие результаты получаются, когда последовательные значения d не кратны друг другу. По этой причине Д. Кнут (Кнут Д. Искусство программирования для ЭВМ. Т. 3. - М.: Мир, 1978. С. 342) указывает, что дистанцию нужно вы­ бирать так:

258

1,4, 13, 40, 121, ... (в обратном порядке)

Анализ показывает, что число сравнений при этом пропорцио­ нально size^'^, а не size^'^ ^ как в нашем варианте. И то, и другое при больших size хуже, чем size-Xogj^size),

15.8. Сложная сортировка обменом (сортировка Хоора)

/. Идея алгоритма (рис. 75). Исходный массив разбивается на два сегмента - левый, элементы которого агг[ i ].кеу <= median.key, и правый сегмент с элементами arr[j [.key >= median.key. Далее, каж­ дый из полученных сегментов можно сортировать автономно, ана­ логично предыдущему, до получения сегментов единичной длины. Тогда массив в целом будет отсортирован.

п

median

median = arr[ (left+right )/2 ]

Рис. 75. Идея алгоритма сортировки Хоора

2. Как выполнить разделение на сегменты? Решение этой задачи представлено на рис. 76.

Анализ рисунка показывает, что за size сравнений {size - число элементов массива) исходный массив разделяется на два сегмента, которые можно сортировать автономно. Всего потребуется Xo^^i^ize) таких разделений, в результате которых получатся сегменты еди­ ничной длины. Следовательно, общее число сравнений пропорцио­ нально size • 1о§2 {size).

259