Лекции по информатике (984119), страница 17
Текст из файла (страница 17)
Сортируемые элементы будем обозначать ал, аа,..., а„. Сортировка есть некоторая перестановка, этих элементов ае,, аг„,..., аь„, гле (lсл, Е<2,..., >с„лгеР<лстановка послеДовательности 1, 2,..., и), для которой выполнено нс которое отношение порядка Г"; Даът) < Г С<а1,) « У(алэ,) В случае, когда элементы ал, а2,..., а„непосредственно сравнимы„отношение порядка Г" вычислять не требуется, а достаточно хранить сами сравниваемые компоненты в соответству.ющих полях элементов ал.
Так же, как и в случае поиска, сравнимые поля элементов сортировки называются ключалли. Типы других компонент элеълентов, хранимых с ключами, могут быть самыми разнообразными, и поэтому элементы обычно имеют комбинированный тип: Суре 1Сеп> — гесогс1 1<еу: ЕНСенег; 1' оггисаниел других ъ:ох<ионе><и>, лг епс1; Итак, клк>ч идентифицирует каждый элемент множества и определяет его итоговое местоположение в упорядочиваемой последовательности. Для исследования алгоритмов 327 сортировки сущсствеш<сн только к:<гоч.
Для простоты мы будем полагать ключ скалярным и, без ограничения общности, целочисленным. Как обрабатывать составные к почи, мы уже знаем на примере поиска в таблицах. Метод сортировки называется устойчивьгм !'стабильным), если в процессе сортировки относительное расположение эл<'ментов с равными ключами не изменяется. Устойчивость сортировки полезна., когда предполагается последунлцсе упорядочивание по вторичным клквгак< среди равнозначных элементов.
Помимо упомянутых классических книг Д. Кнута, Н. Вирта и Г. Лорина, сортировки достаточно подробно рассматриваются в недавно изданных учебниках Массачусетского Технологического Института [85[ и Принстонского университета [88[. Хорошая книга Лхо, Хопкрофта и Ульмана отличается примерами на стандартном Паскале [90[. 6.2.2 Сортировка массивов Основное ограничение внутренней сортировки традиционно было связано с дефицитной оперативной памятью. Это означает, что перестановки элементов в процес<е сортировки должны выполняться на месте, без использования вспомогательных массивов.
Другим критерием экономичности алгоритма сортировки является временная сложность, которую мы будем выражать в виде функции 1 (С(п), Ч (и)), где и — <исло сортируемых элементов, С число сравнений ключей и ЛХ число перестановок !пересылок) элементов. Сравнения и пересылки рассматриваются отдельно, поскольку их времена могут отличаться существенно. Рассмотрение алгоритмов сортировки начнем с т. н. прямых методов. С этих простых и неэффективных методов началась история и эволюция сортировок. 6.2.2.1 Сортировка вставкой Этот метод широко используется при игре в карты: игрок обычно располагает имеющиеся карты в левой руке веером в порядке возрастания ранга, а сдаваемая карта вставляется сообразно ее рангу после последней карты того же ранга.
Сортировка вставкой (огга же сортировка прямым включением) представляет собой вариант этой карточной идеи. Сортируемые элементы мысленно делятся на уже готовую (отсортированную) последовательность а,,..., а<, и исходную (неуггорядоченную) последовательность а,,..., а„. Вначале первая последовательность должна быть пуста, по мы включим в нее первый элемент множества, поскольку последовательность из одного элемента всегда упорядочена. 'Этот элемент не обязательно миггимальный, и вгюследствии он может быть переставлен на подобающее место. Схема алгоритма сортировки вставкой такова: гг Неупорядоченная. последовательность простирается от г,'— ого до и — ого элементов 7' Гог 1: - 2 1о и <1о Ьеи1п х:-- а[< [; 1' Вставка элемента я в последовагпеаьность а[1..г~ ) еп<1; Ниже приведен пример работы алгоритма прямой вставки для последовательности 44 55 12 42 94 18 06 67 (встагглег<ны<; элок<виты выделены полужирным шрифтом, вставляемые курсивом): Исходные ключи 1=2 1=3 1=4 1=5 1=6 1= 7 1=8 44 бб 12 42 94 44 55 19 12 94 12 44 55 42 94 12 42 44 55 94 12 42 4.4 55 94 12 18 42 44 55 06 12 18 42 44 06 12 18 42 14 18 06 67 18 06 67 18 06 67 18 06 67 18 06 67 94 0б 67 55 94 б'7 55 67 94 В схеме алгоритма мы намеренно нс уточнили процесс поиска подходящего места для вставки, поскольку он может быть организован по-разному.
Рассмотрим сначала пример, когда поиск идет с на |ада отсортированной подпоследовательности, т. е. слева направо. ргосес1пге Всг8е!ЕавуЯог1(айаг а: гес1); 1' Сортировка прямой вставкой — упрощенный алгоригпм 3 айаг 1, 1, 1с: шс1ех; х: 11,епц Ьеиш Еог 1:-- 2 $о и с1о Ьеиш х: а[1]; Е' 1 — тый элемент исходной последовательности копируется в х / Е' Поиск места для всгпавки идегп слева направо у жЬЕЕе (а[1[ < х) апс1 Д < 1) с1о 3: 3 ч-1' Е' Место длгя вставки найдено, 1' — тый элекиепт — первый, больший х 3 Е' Сдвигаем хвост, упорядоченной последовательности — йсно сдвига, 0(п) 7' Ког Ес:--- 1 сЕоипФо1 сЕо а[Ц: — а [1с — 11; а[1[: — х; Е' Вставляем извлеченный элемент на освободившееся от сдвига место. Сдвиг продолзсается вплоть до элемепгпа, где ро,ньте был х 3 епсЕ; епс1; Умножая общее число сдвигов и, — 1 на цену сдвига п,~2 получим квадратичную сложностиую оценку 0(п~).
Такая высокая цена вызвана частыми групповыми операциями (сдвигами) и обращением с массивом как с последовательностью. ЕЕа самом деле поиск места для вставки удобно осуществлять справа налево, чередуя сравнения и движения по упорядоченной последовательности, как бы просеивая вставляемый элемент х = а; через разноячеистое сито упорядоченной подпоследовательности (движение справа налево позволяет выполнять необходимые сдвиги в процессе поиска,, а не после него; иногда сдвигов не бывает вообще, когда элемент головы неупорядоченной потшоследовательности включается в хвост упорядоченной без каких-либо персмещений). То есть х сравнивается с очередным элементом а, а загсм либо помещается на место а д, если а < х, либо элемент а помещается на место 1 Е 1 (сдвигается).
Место 1+ 1 свободно, поскольку либо 1+ 1 = 1 (на первом шаге), а, элемент массива а; уже продублирован в переменной х, вследствие чего запись на 1-тую позицию не приведет к потере, либо, на послееДУюпеих шагах, элемент на этой позиции Уже записан на позицию 1' + 2 (в силУ первого шага). Итак, просмотр упорядоченной подпоследовательпости происходит справа палево и заканчивается по одной из следующих п1>ичин: 1, найден элемент а с к.почом, меньшим ключа х, 2. достигнут левый конец последовательности. Доказательство корректности и завершимости алгоритма вставки может быть выполнено индукцией по длине упорядоченной тюдцоследовательности.
База индукции: последовательность из одного элемента упорядт>чена. Гипотеза: вставка превращает упорядоченную последовательность длины Й вЂ” 1 в упорядоченную тюследовательность длины Й: в силу оттределения вставки на каждом шаге происходит добавление в последовательность только одного элемента, причем он записывается сразу за последним элементом а < .тх бытт. может, в конец упорядоченной подпоследовательности, а сл ( а д вследствие способа выбора места вставки, т. е. устойчивая упорядоченность элементов сохраняется.
Таким образом, по исчерпании неупорядоченных элементов вся последовательность будет отсортировапа. ргосес1пге Бсг1пвБогт[л аг а: вес1); 1' Сортировка прямой вставкой — сптапдарттлый алгортипм ~ 1' Основной принцип: полагая., что первые л — 1 элементов отсортпированы, берем л — й элемент и вставляем его на нужное место тт айаг 1, 1: шс1ех; х: 11еш; Ьеиш 1ог 1: 2 $о и с1о Ьеи1п х: — а[1]: 1' т' — тпый элементп исходной последовательности коптсруется в л тт 1' Фиксируем стпартовую позицию для поиска справа налево у 1' Сдвигаем элементы вправо 3 итЬ11е (аЦ вЂ” 1~ > х) апс1 Ц ..= Ц с1о Ьеиш а[~ ~:- - а[1 — Ц; 3: 3 епс1; а,[~ [: - х; 1 БстаалЯсм на, нУэюное место тт епс1; епс1; ргосес1пге БйгЯе!Бог1В(айаг а: встс1); 1' Сортптсровка прямой встаснтой — алгоритм с барьером тт 1' Основной принципа барьер упросцаст сравтсстте и ускоряет сортпировку у' 1' Недостаток: присаодитпся нарасциеиипь структуру данпысс на 1 элемент тт айаг 1, 1': 1пс1ех; х: йеш; Ьеиш 1ог 1; - 2 $о гт с1о Ьеи1п х: а[1[; а[0~:=- х; тт аттО) — барьер тт 1: гг Коиггроваиие со сдвггаом 3 гчЬ11е [а[1 — Ц > х) с1о Ьеиш аЦ ]:-- аЦ вЂ” 1]; 3: — 3 — 1; епс1; а,(]]: х; 1' Бсгпавгглам на освободгигговеся место гг епс1: епс1; Проанализируем метод вставки.
Число сравнений ключей С, па г,-том этагге находится в диапазоне от 1 до г — 1, в среднем г/2. Число перестановок элементов ЛХг равно С;+ 2 [вклгочая барьер). Поэтому общее число сравнений и перестановок таково: Минимальные оценки метода вставки достигаются в случае уже упорядоченной исходной последовательности. Псгскольку поиск идет справа налево, наихудшая производительность имеет место, когда сортируемые элементы располагаются в обратном порядке, что влечет сдвиги максимальной величины. Сортировка вставкой демонстрирует некоторое естественное постепенное упорядочение, когда, в каждый момент времени у нас имеется частично отсортированная последовательность с полностью отсортированной поднос:ледовательностью в начале.
Кроме того, приведенный алгоритм сортировки вставкой устойчив. Алгоритм с ггрямой вставкой можно легко улучшить, зная об упорядоченности выходной подпоследовательности. В этом случае поиск места для вставки может быть существенно ускорен за счет ггрименения бинарного поиска в упорядоченной части последователыюсти. Такой поиск возможен. поскольку она располагается в памяти прямого доступа. Соответствующая модификация алгоритма называется методом двоичной вставки. Приведем программу сортирогзки этим методом: ргосес1ше Вгп1пвВогг[тгаг а,: весг); 1' сорпигровка двоичной вставкой гг чнг 1, 1, 1., К., ш: и~1ех; х: йепц Ьедш Гог 1 и 2 Фо п с1о Ьеиш х: - а(1]; Ь:=- 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
