Главная Промышленная автоматика.

ГЛАВА 8

Сортировка

Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение "<" для чисел. Это очень большая тема, поэтому она разбита на две части: внутреннюю и внешнюю сортировку. При внутренней сортировке все сортируемые данные помешаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке (т.е. используется модель памяти с произвольным доступом). Внешняя сортировка применяется тогда, когда объем упорядочиваемых данных слишком большой, чтобы все данные можно бьшо поместить в оперативную память. Здесь узким местом является механизм перемешения больших блоков данных от устройств внешнего хранения данных к оперативной памяти компьютера и обратно. Тот факт, что физически непрерывные данные надо для удобного перемешения организовывать в блочную структуру, заставляет нас применять разнообразные методы внешней сортировки. Эти методы будут рассмотрены в главе П.

8.1. Модель внутренней сортировки

В этой главе мы представим основные принципиальные алгоритмы внутренней сортировки. Простейшие из этих алгоритмов затрачивают время порядка О(л) для упорядочивания и объектов и потому применимы только к небольшим множествам объектов. Один из наиболее популярных алгоритмов сортировки, так называемая быстрая сортировка, выполняется в среднем за время 0(п logn). Быстрая сортировка хорошо работает в большинстве приложений, хотя в самом худшем случае она таюке имеет время вьшолнения О(п). Сушествуют другие методы сортировки, такие как пирамидальная сортировка или сортировка слиянием, которые в самом худшем случае дают время порядка 0(п logn), но в среднем (в статистическом смысле) работают не лучше, чем быстрая сортировка. Отметим, что метод сортировки слиянием хорошо подходит для построения алгоритмов внешней сортировки. Мы также рассмотрим алгоритмы другого типа, имеюшие обшее название "карманной" сортировки. Эти алгоритмы работают только с данными определенного типа, например с целыми числами из ограниченного интервала, но когда их можно применить, то они работают очень быстро, затрачивая время порядка 0(п) в самом худшем случае.

Всюду в этой главе мы будем предполагать, что сортируемые объекты являются записями, содержашими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что на нем определено отношение линейного порядка "<". Целые и действительные числа, символьные массивы - вот обшие примеры таких типов данных, но, конечно, мы можем использовать ключи других типов данных, лишь бы на них можно было определить отношение "меньше чем" или "меньше чем или равно".

Задача сортировки состоит в упорядочивании последовательности записей таким образом, чтобы значения ключевого поля составляли неубываюшую последовательность. Другими словами, записи ri, г, ...» г„ со значениями ключей ki, k2, k„ надо расположить в порядке г, г,г, , таком, что fe, \ < . Мы не требуем,

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



Мы будем использовать различные критерии оценки времени выполнения алгоритмов внутренней сортировки. Первой и наиболее общей мерой времени выполнения является количество щагов алгоритма, необходимых для упорядочивания л записей. Другой общей мерой служит количество сравнений между значениями ключей, выполняемых при сортировке списка из п записей. Эта мера особенно информативна, когда ключи являются строками символов, и поэтому самым "трудоемким" оператором будет оператор сравнения ключей. Если размер записей больщой, то следует также учитывать время, необходимое на перемещение записей. При создании конкретных приложений обычно ясно, по каким критериям нужно оценивать применяемый алгоритм сортировки.

8.2. Простые схемы сортировки

По-видимому, самым простым методом сортировки является так называемый метод "пузырька".Что/бы описать основную идею этого метода, представим, что записи, подлежащие сортировке, хранятся в массиве, расположенном вертикально. Записи с малыми значениями ключевого поля более "легкие" и "всплывают" вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход снизу, берется первая запись массива и ее ключ поочередно сравнивается с ключами последующих записей. Если встречается запись с более "тяжелым" ключом, то эти записи меняются местами. При встрече с записью с более "легким" ключом эта запись становится "эталоном" для сравнения, и все последующие записи сравниваются с этим новым, более "легким" ключом. В результате запись с наименьщим значением Ключа окажется в самом верху массива. Во время второго прохода вдоль массива находится запись со вторым по величине ключом, которая помещается под записью, найденной при первом проходе массива, т.е. на вторую сверху позицию, и т.д. Отметим, что во время второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи, меньщие, чем у оставщихся записей. Другими словами, во время j-го прохода не проверяются записи, стоящие на позициях выще /. В листинге 8.1 приведен описываемый алгоритм, в котором через у1 обозначен массив из п записей (тип данных recordtype). Здесь и далее в этой главе предполагаем, что одно из полей записей называется key (ключ) и содержит значения ключей.

Листинг 8.1 .Алгоритм „пузырька"

(1) for i:= 1 to л - 1 do

(2) for j: = 1 downto i + 1 do

(3) \f A[j] .key< A[J - IJ./reythen

(4) swap([j] , A[J - 1])

Процедура swap (перестановка) используется во многих алгоритмах сортировки для перестановки записей местами, ее код показан в следующем листинге.

Листинг 8.2. Процедура swap

procedure swap ( var x, у: recordtype ) { swap меняет местами записи x ж у } var

temp: recordtype; begin

temp:= X;

x:= y;

y: = temp; end; { swap }



Пример 8.1. В табл. 8.1 приведен список названий и годы знаменитых извержений вулканов.

Таблица 8.1. Знаменитые извержения вулканов

Название

Пили

1902

Этна

1669

Кракатау

1883

Агунг

1963

Св. Елена

1980

Везувий

Для этого примера мы применим следуюгцее объявление типов данных: type

keytype = array[1..10] of char; recordtype = record

key: keytype; { название вулкана } year: integer { год извержения }

end;

Применим алгоритм "пузырька" для упорядочивания списка вулканов в алфавитном порядке их названий, считая, что отношением линейного порядка в данном случае является отношение лексикографического порядка над полем ключей. В табл. 8.2 показаны пять проходов алгоритма (в данном случае п = 6). Линии указывают позицию, выше которой записи уже упорядочены. После пятого прохода все записи, кроме последней, стоят на нркных местах, но последняя запись не случайно оказалась последней - она таюке рке стоит на нужном месте. Поэтому сортировка заканчивается.

Таблица 8.2. Сортировка методом „пузырька"

Агунг

Пили Этна

Кракатау Агунг Св. Елена

Везувий

Пили Этна Кракатау Везувий

Агунг Везувий

Пили Этна Кракатау

Агунг Везувий Кракатау Пили Этна

Св. Елена

Св. Елена Св. Елена Св. Елена Этна

Агунг Агунг

Везувий Везувий Кракатау Кракатау Пили Пили

Св. Елена

Этна

Начальное положение 1-й проход 2-й проход 3-й проход 4-й проход 5-й проход

На первом проходе Везувий и Св. Елена меняются местами, но далее Везувий не может поменяться местами с Агунгом. Агунг, поочередно меняясь местами с Кракатау, Этной и Пили, поднимается на самый верх. На втором этапе Везувий поднимается вверх и занимает вторую позицию. На третьем этапе это же проделывает Кракатау, а на четвертом - Этна и Св. Елена меняются местами, Пили стоит на нркном месте. Все названия вулканов расположились в алфавитном порядке, сортировка закончилась. Пятый этап также выполнен в соответствии с алгоритмом листинга 8.1, но он уже не меняет порядок записей. П





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 [72] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0025