Лекции по информатике (984119), страница 19
Текст из файла (страница 19)
Говоря о быстром всплытии легкого пузырька, мы одновременно можем констатировать ме,членное погружение тяжелого. Как сказал проф. Д. Ь. Подшивалов, всплывает пузырек сразу, за один проход, .а тонет медленно, только на один уровень за проход. Еще одна цитата в тему: «Один плохо расположенный пузырек на, тяжелом конце в массиве с обратным порядком быстро перемещаются на нужное место, а также неудачно размещенный элемент на легком конце медленно просачивается к своему окончательному положению» ]54]. Такая ассимметрия пузырьковой сортировки вызвана особенностью происходящих парных обменов и направлением просмотра, при которых меньший элемент снова, участвст в сравнении в качестве члена следунлцей пары и имеет шанс таким образом быстро «проскочить в дамки».
В то же время ббльшие элементы остах>тся на, месте без дополнительного внимания до следующего прохода, где у них, в случае проигрыша,, снова не будет возмолености быстрого продвижения к поверхности. Е1апример, массив 12 18 42 44 55 67 94 06 с помощью усовершенствованной пузырьковой будет упорядочен за 2 просмотра, а для сортировки массива 94 06 12 18 42 44 55 67 потребуется 8 проходов. Это наводит на, мысль чередовать направления просмотра с целью дальнейшего ускорения сортировки.
Технически чередование выписывается явно или могло бы быть реализовано чередованием прямого и обратного итераторов обхода массива, для которых по-разному определено направление просмотра, «вперед». В честь бармен- ского приспособления для встряхивания (с переворачиванием! ) коктейлей, модернизированная пузырьковая сортировка названа >аейкерной. Шейкерная сортировка столбца даст следующие результаты: 1 2 3 3 4 4 Л, 8 8 7 7 4 ь т ~ т ~ т 44 06 06 06 06 55 44 44 12 55 12 44 18 42 12 42 18 42 94 42 55 42 44 18 94 18 55 55 06 18 67 67 67 67 67 94 94 94 Программа тцейкертюй сортировки итсрирует линейную композицию из прямого и обратного прохода: ргосес1пге 81та,1сегЯогт[чаг а: аес11„ 1' Сортпировка ттрямым обменом — тейкерная ~ 1' Основной принцип: на каэтсдом проходе сравниватотпся два соседних элемента и обмстниваются местами, Обмсп идспт в двух направлениях. Приметтяется: если известпно, что элементы почтпи упорядочены т айаг т, 1, 1с, 1., К: тттс1ех; х: Мент; Ьеиш Ь : — 2; К:= и; 1с:== и; гер еаза Гог 1:--=- К с1отчпФо Ь с1о 1т а[1 — Ц > а[1[ сЬеп Ье~1п х: — аЦ вЂ” Ц; а[1 — Ц: а[11; а[1[: -- х; 1т: — ~ 1' Усовсртоентпвовпнный впртлантпт запоминается последний, обмен т' епс1; 1.: — ~'+ 1; Гаг 1: ЬФо Кс1о Г ат,[т — Ц > а[т1 $1теп Ьеиш х: а[1 — Ц; а[1 — Ц: — аЦ ~:, а[11: — -- х; 1с: -- т 1' Усоверитеттстпвованный вариант: запоминается, последний обмен т епс1; К:.
1с — 1; нп011 >К:, епс1; Проанализируем обменные сортировки. Число сравнений в простейшем варианте и — и 2 а минимальное, среднее и максимальное число перестановок элементов равно соотвест- венно "~>1»тп 3(>г' — и) - О1я 4 3(ггг — и) >11>~>и>::— 2 Анализ улучшенных обменных методов, особенно шейкерного, более сложен. Минимальное число сравнений С,„= гг — 1. Д.
Кнут считает !65>~, что среднее число проходов улучшенной пузырьковой сортировки 0(п, — 'к:г,/п), а среднее число сравнений п2 — пЯэ 1!пп) 01 2 ). 11о главное все перечисленные усовершенствования не влияют на число перестановок. Они лишь сокращают количество избыточных двойных проверок. А ветл. обмен местами двух элементов, как правило, дороже сравнения ключей. Кроме того, все эти усоверпгеыствования не снижают квадратичного порядка алгоритмической сложности обменных сортировок: все улучшения являются константными или алдитивными термами квадратичной доминанты. Фактически, обмен>сан сортировка и ее усовершенствования занимают некоторую среднюк> позицик> между простыми и ресурс:оеъгкими сортировками вставкой и выборкой.
Только шейкерная с:ортировка дает выигрьпп в случае почти упорядоченного массива,, например, когда осущс с:твляются редкие вставки в отсортированный массив. Можно показать, что среднее расстояние, на которое должен продвигаться каждый из и, элементов во время любой сортировки, равно и/3 позиций !65). Поэтому простые методы сортировки, продвигающие элемент на одну позицик> за шаг, квадратичны и неудовлетворительны. Серьезного улучшения скорости сортировки можно достичь только перемещая сортируемыс элементы на, болыпие расстояния в каждом такте. Перейдем к рассмотрению существенных улучшений изученных нами простых методов сортировки.
6.2.2.4 Сортировка Шелла В 1959 г. Д. Шеллом было предложено усовершенствование сортировки вставкой. Для ускорения он пре с„>гожизг выделять в сортируемой последовательности периодические поднос:.чедовательности рег1лярного шага> в каждой из гсото1эых отдельно выполняется обычная (или двоичная) сортировка вставкой. Эти подпоследовательности пронизывают крупными стежками век> сортирусмую последовательность и, по построению, дают большие перемещения элс;ментов. Ввиду регулярного шага (псргсода) и прямого доступа к элементам массива (инде>гсс>и1эованного, конечно жс., целым типом) гг1эохождение этих подпоследовательностей реализуется циклом с параметром Ког.
После каждого прохода шаг подпоследовательностей умс;ныпается и сортировка повторяется с новыми прыжками, причем переход к меньшему шагу не только нс требует затрат на организацию новых подпоследовательностсй,. но и не ухудгпает сортирс>ванность упорядочиваемого массива (тс>орекса К и, 5,2.! в книге !65~ и лемма 6. 7 в книге ~88~). Пос ледней выполняется сортировка с шагом 1, ггодчигггаюгцая огрехи прсдыдугцих проходов.
При кратном умсныггении шага» нап1эиме1г, 8 4 2 1 мы в конце концов получим две автономные подпоследовательности и на завершающем проходе нам придется «много вставлять». Избежать этого можно., по рецепту Д. Кнута, используя последовательность 1 4 13 40 121 364 1093 3280 9841 ... Зп + 1 Эта, последовательность приводит к хоропгому «перемепгиванию» организуемых подпоследовательностей и сводит к минимуму их изолированность, и на последней стадии сериализации вставка будет идти почти без ресурсоемких сдвигов.
Наверное, сортировка Шелла может базироваться и на других простых методах, но метод вставки из них не только относительно быстрый, но и обладает позитивной реакцией на, частичную упорядоченность последовательности, которая имеет место в результате предыдущих проходов. Но установлено, что оптимальные расстояния не должны быть множителями друг друга, чтобы не образовывать автономно сортируемых непересекающихся цепочек. Более того, взаимопроникновение различных цепочек должно быть максимизировано. Приведем пример сортировки Шелла: Исходные ключи 44 55 12 42 94 18 06 67 Сортировка с шагом 4 44 18 06 42 94 55 12 67 Сортировка с шагом 2 06 18 12 42 44 55 94 67 Сортировка с пгагом 1 06 12 18 42 44 55 67 9'1 Выигрыш сортировки Шелла происходит за счет того, что на каждом этапе либо сортируется относительно мало элементов, либо эти элементы уже довольно хорошо упорядочены и происходит сравшпельпо немного перестановок, к тому же и на расстояния » 1.
ргосес1пге 81ге118огс(ггаг а: весг); г' Соргаировка Шелла зг 1' Основной ггринцгт: сортировка вставкой для элементов, отстоящих на Ь(р~ позиций. Проходы для Цр] -- 9, 5, 3, 1 7' сопв$1 - 4; к'аг г, 1, 1г: 1ггс1ех; ш: Ых; х: сепг; 1г: аггау~1..1~ оГ денег:, Ьен1п 1)~Ц: 9:, 5~21; 5; 11 (31: 3: 1г ~4]: 1:, Гог ш:-- 1 Со 1 с1о Ьен1п 1: - Цпг1; 1 Сортируем, вспижкой субсериализировогнаый массив г Гог 1:-- 1, 1 $о и г1о Ьен1п 340 х: а[г[; ягЫ1е [х < а[[[) апс1 [) > 1) с1о Ьеи1п а[) .- Ц г — а[) [; епс1; аЦ Ц: х; епс1: епс1: епс1; В книге Н. Вирта [54[ приведен барьерный вариант такой программы, упрощающий условие окончания места для вставки, причем для каждой из подпоследователыгостей нужен своП барьер, пристраиваемый слева от края массива.
Число барьеров равно максимальному шагу. Проанализируем метод сортировки Шелла. Недостатком сортировки Шелла является ее неустойчивость. Кроме того, сортировка Шелла может привести к резонансному явлению [трсгпингу) в системах с виртуальной памятью, когда члены последовалгелыгосги попадают на разные страницы виртуальной памяти. Математический анализ сортировки Шелла исключитеггыю сложен. Абсолютно оптимальные последовательности уменьшающегося шага до сих пор не построены. Но в современной монографии Седжвика [88[ приведено несколько очень хороших результатов: Общая степенная сложностная оценка сортировок Шелла 0(и' ~), где 0 < гг < 1, даже при малых о (скажем, 10 в) асимптотически хуже линеарифмической и 1ояп и и 1од" и. Но одпсгвреыенпо сортировка Шелла существенно быстрее простых сортировок с их квадратичной сложностью.
6.2.2.5 Пирамидальная сортировка Сортировка выборкой была основана, на повторяющемся поиске наименьшего ключа в постепенно сокращаннцейся последовательности элементов, Несмотря на то, что число сравнений в последующих проходах умсныпалось (гг — 1, и — 2, ... ), .оно все равно остас"тся ггг, — и г' 2 квадратичным ~ . Причина такой высокой трудоемкости сортировки выборкой 2 в том, что при ~оиске минимального элемента на каждом проходе теряется ценная информация о друтих почти минимальных элементах. Дело в том, что поиск линейный, и его результат — единственное скалярное значение, никаких пометок, закладок, флажков, тегов в просматриваемой последовательности не ставится, она остается линейной и не приспособленной к сокращению перебора структурой. Существует модификация сортировки выборкой, оставляющая после каждого прохода гораздо больше порядковой информации, чем просто минимальное значение.
В сортируемом множестве можно сравнить пары соседних элементов. В результате п,г2 сравнений мы получим такое же число победителей элементов с меньшими ключами. Если среди победителей провести такое же сравнение, мы получим»/4 меньших элементов. Продолжая процесс ~1оц и) -1 1 раз, и проделав п — 1 сравнение., мы получим дерево выбора минима:>ышго элек>епта.
Кстати, дерево выбора эффективно реализует очередь с приоритетами, с той лишь разницей, что наибольшему приоритету соответствует наименыпий ключ элемента, помсщаемого в вершину дерева. Дерево выбора Раньше мы довольствовались только минимальным элементом - корнем дерева, теперь древовидная структура сохраняет турнирную историю этой своеобразной игры в поддавки и может быть использована для сокращения перебора сортируемых элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
