AOP_Tom3 (1021738), страница 45
Текст из файла (страница 45)
В4. [Были лн обмены7] Если 1 = О, завершить выполнение процедуры. В противном случае присвоить ВОУйО < — 1 и возвратиться к шагу В2. ) Рис. 15. Блок-схема сортировки методом пузырька. 426 653 275 897 170 ' 908 Ю 061 512 х 087 503 154 426 653 275 897 г 170 512 061 503 мг 087 509 : 612 154 ' 509 426 1э4 653 Ф 426 275 512 Ф' 512э~ 275 170 , 503 е' 503 е 170 061 087 У 087ме 061 612 512 509 154 426 503 г 275 170 087 061 612 612 512 512 509 509 503 503 426 426 275 275 Программа В (Метод пузырька).
Как и в предыдуших Н1Х-программах этой гла- вы, полагаем, что сортируемые записи находятся в ячейках от 1МРОТ+1 до 1ИРОТ+И. гП = 1; г12: — 1. 01 БТАНТ ЕИТ1 И 1 В1. Инн налили рвать ВООИО. 4 е- 1У. 09 1Н ЯТ1 ВООИР(1: 2) А 00 ЕИТ2 1 А 04 ЕМТ1 О А 05 ЛИР ВООМО А 00 ЗН ЕОА 1ИРОТ,2 С 07 СИРА 1МРОТ+1,2 08 11Е 2Г 09 1.0Х 1ИРОТ+1,2 10 ЯТХ 1ИРОТ,2 11 ЯТА 1МРОТ+1,2 1О ЕИТ1 0,2 1У 2Н 1МС2 1 14 ВООМО ЕМТХ -е,2 15 ЗХМ ЗВ 16 4Н .11Р 1В ВООВО +- а вг. ГЬ еЗ А !+- О. Выход, если 1 > ВООВО. ВЗ. С веление и нли обмен В: В ~~ С С Нет обмена, если Кэ < Км ь В Яеы В -+ В,. В (Прежнее В ) -~ В еь В 1е- 1) С !+-!+1.
А+ С гХ+- 1 — ВООВО. (Модифицируемая команда] А+ С Выполнять шаг ВЗ для г 1 < 1 < ВООВО. А В4. Нет обменов? Перейти к шагу ВЗ, если!>О. 4 Теорема 1. Пусть а, ае... а„- — перестановка множества (1, 2,..., и), а Ь, Ьз... ܄— соответствующая таблица ннвсрсой, Если в результате очередного прохода прн сортировке методом пузырька (алгоритм В) перестановка а1 ае... а„преобразуется в а! а~э... а„', то соответствующая таблица !гнверснй Ь', Ьз...
Ь'„получается пз Ь! Ьз... Ь„ и результате уменьшения на единицу каждого ненулевого элемента. Доказательство. Если перед а, имеется болыпий элемент, то а; поменяется местами с наибольшим нз предшествующих элементов, так что Ь,, уменьшится на елиницу. С другой стороны, если перед а, нет элемента, болыпего а„то а; никогда не поменяется местамн с большим элементом, так что Ь„останется равным нулю. 1 Анализ метода пузырька. Очень полезно исследовать время работы алгоритма В. Оно определяется тремя параметрами: числом проходов А, числом обменов В и числом сравнений С.
Если исходные ключи различны и расположены в случайном порядке, можно предположить, что они образуют случайную перестановку множества (1,2,...,п). Понятие таблица инверсий (раздел 5.1.1) приводит к простому способу описания эффекта, достигаемого на каждом проходе при сортировке методом пузырька. Итак, можно разобраться в том, что происходит в процессе сортировки методом пузырька, изучая последовательность таблиц инверсий между проходами. Вот как выглядят, яапример, таблицы инверсий для рис. 14.
3 1 3 3 4 5 0 4 0 3 2 2 3 2 1 Проход 1 2 0 7 2 3 4 0 3 О 2 1 1 2 1 0 Проход 2 106123020100100 Проход 3 005012010000000 Поэтому, если 6| Ьз... ܄— таблица инверсий исходной перестановки, то должны выполняться равенства Л = 1 + |пах (6|, 62,..., Ь„), В = 6, + Ьт + ". + Ььч С=с|+со+ +од, (2) (3) (4) где су — значение ВООИΠ— 1 перед началом у-го прохода. Используя таблицы инверсий, запишем Теперь можно вычислить среднее значение 2 ЬАь.
Выполнив суммирование по частям, получаем ,~" 6"-ьЬ! А„„, =и+1 — 5 ' =и+1 — Р(н), ~.-/ и | ь=о (7) где Р(п) — - функция, асимптотическое поведение которой, как следует из соотношения 1.2.11.3- (24), описывается формулой;/ьпп/2 — $ + 0(1/э/й). Формула (7) была представлена без доказательства в работе Е, Н.
Рг|еп|1, ХАС61 3 (19об), 150; доказательство в своей докторской диссертации привел Говард Б. Денут (Нежат|1 В. Вешп|Ь) [РЬ. П. ТЬе|йз (асан(от|1 1)в|мега|у, Ос|оЬег, 1956), 64.-68]. Стандартное отклонение величины Л представлено в упр. 7. Проанализировать суммарное число сравнений С несколько сложнее, поэтому рассмотрим только среднее значение С~„,. Пусть /1(6) —. число таких таблиц инверсий Ь|...Ь„(п фиксировано), что при 1 < |' < и либо 6| < у — 1, либо 6|+| — у < Ь; тогда /уй) — (у+")~(з — 1)" ' ' (см. упр. 8).
Среднее значение с, в (5) равно по частям, а затем по у, получаем формулу С.„=(" ) — -', Е /,(6)= |<|<о дляО<6<п — | (8) (~ , 'Й(/,(6) — /эЯ вЂ” 1)))/и!. Суммируя (и+ 1) 1 (9) о<г«*в о<|< -| Определить асимптотическое значение здесь не так просто, и мы вернемся к нему в конце этого раздела. Подводя итог анализу метода пузырька, запишем формулы, выведенные выше (а также ниже), следующим образом: с, = |пах (6|+ г ~ Ь, > | — 1) — у (5) (см.
упр. 5). Следовательно, в примере (1) А = 9, В = 41, С = 1о+ 14+ 13+ 12+ 7+ 5+ 4+ 3+ 2 = 75. Общее время сортировки на машине К1Х для шгучая, показанного на рис. 14, равно 96Ои. Распределение величины В (суммарного числа инверсий в случайной перестановке) нам уже хорошо известно; значит, остается проанализировать величины А и С. Вероятность того, что А < Ь, равна произведению 1/и! и числа таблиц инверсий. НЕ СОдЕржащИХ КОМПОНЕНТ > 15 а ИМЕННΠ— — Ьч ЬЫ При 1 < 6 < Н.
СЛОдОВатЕЛЬНО, вероятность того, что потребуется ровно Ь проходов, равна Ль = †, (6"-" 6| — (6 — Ц"-' '(6 — Ц,). (6) А = (пип 1, аче Х вЂ” ~/яМ/2+ 0(1), шах Х); В = (пип О, ате -'(Х вЂ” Х)., шах -'(Ж вЂ” д')); (10) С = (пип Х вЂ” 1, ате ~1 (Ю вЂ” Х !в Х вЂ” (7 +! и 2 — 1) Ю) + 0 ( т/Х ), шах -',(Х вЂ” Х)). (12) Во всех случаях минимум достигается, когда исходная последовательность записей уже упорядочена, а максимум — когда записи расположены в обратном порядке.
Таким образом, время работы для машины М11 равно 8А+ 7В+ 8С+ 1 = (ш!и 8%+ 1, ате 5 75№+ 0(й!окг1), шах 75№+ 05Х+ 1). Модификация метода пузырька. Мы потратили много усилий на анализ метода пузырька, и„хотя способы, применявшиеся при вычислениях, поучительны, результаты разочаровывают, поскольку они говорят о том, что метод пузырька вовсе не так уж хоросп. По сравнению с простыми вставютми (алгоритм 5.2.18) метод пузырька описывается более сложной программой и требует примерно в 2 раза больше времени! Можно предложить несколько путей улучшения метода пузырька. Например, на рис. 14 первое сравнение на проходе 4 лишнее, так же как и два первых сравнения на проходе 5 и три первых на проходах 6 и 7.
Заметим, кроме того, что за один проход элемент не может переместиться более чем на одну позицию влево; так что если наименьшие элемент вначале был крайним справа, то придется выполнить максимальное чигло сравнений. Это наводит на мысль о "шейкер-сортировке", ко~да последовательность записей просматривается попеременно в обоих направлениях (рис. 16). При таком подходе среднее число сравнений несколько сокращается.
К. Э. Айверсон (см. К. Е. 1чегаоп, А Ргобгашпйпб Ьапбиабе (%!!еу, 1962), 218-219) сделал интересное в этом отношении наблюдение: егши З' — такой индекс, что В! и В +~ не меняются местами на двух последовательных проходах в противоположных направлениях, то записи Л, и В,+1 должны занимать свои окончательные позиции и их можно исключить из последующих сравнений. Например, просматривая перестановку 4 3 2 1 8 6 9 7 5 слева направо, получаем 3 2 1 4 6 8 7 5 9; записи В~ и Вэ не 1юменялись местами. При просмотре последней перестановки справа налево Вл все еще меныпе записи йь (новой записи).
Следовательно, можно сразу же сделать вывод о том, что записи Вт и Ль могут и не участвовать ни в одном из последующих сравнений. Однако ни одно из этих усовершенствований не приводит к лучшему варианту алгоритма, чем алгоритм сортировки методом простых вставок, а мы уже знаем, что даже он не годится при больших Х. Другая идея состоит в том, чтобы избегать большинства обмеяов. Так как большая часть элементов во время обменов просто сдвигается на один шаг влево, можно было бы достичь того же эффекта, рассматривая массив иначе: сместив базу индексирования! Но полученный алгоритм не превосходит метода простого выбора (алгоритм 5.2.38), о котором речь пойдет несколько ниже. Короче говоря, метод пузырька, кажется, не обладает никакими достоинствами, за которые его можно было бы порекомендовать, если не считать легко запоминающегося названия и интересных теоретических задач, к которым он приводит.
703 , 908 908 908 908 908 908 908 765 ; 703 ъ 765 677 ,' 765 703 , 897 897 897 897 897 765 765 765 765 765 677,' 703 612 ' 677 703 703 677 677 703 703 677 677 612 ' 677 509 ' 612 612 653 653 612 612 512 512 612 509 653 l 426 512,Ф 275 503 653 509 426 '« беЗ 275 ь 512 170 «« 503 509 509 503 503 426 426 275 275 170 170 170 154 087 154 087 061 154 154 087 087 061 061 061 061 Рис. 16. Шейкер-сортировка. Параллельная сортировка Бэтчера. Чтобы получить алгоритм обменной сортировки, время работы которого имеет порядок, меныний №, необходимо подобрать для сравнений пары несоседнии ключей (Кн К2); иначе придется выполнить столько операций обмена записей, сколько инверсий имеется в исходной перестановке.
Среднее число инверсий равно 2 (2х'а — Л'). В 1964 году К. Э. Бэтчер (см. К. Е. ВаСсЬег Ргос. 21ГХРБ Ярг2пб Ло2пс Сотри1ег СопГегепсе 32 (1968), 307-314] открыл интересный способ программирования последовательности сравнений, предназначенной для поиска возможных обменов. Его метод далеко не очевиден. В самом деле, обосновать его справедливость весьма сложно, поскольку выполняется относительно мало сравнений. Рассмотрим два доказательства: одно в этом разделе, а другое— в разделе 5.3.4. Схема сортировки Бэтчера несколько напоминает сортировку Шелла, но сравнения выполняются по-новому, а потому цепочки операций обмена записей не возникает.
В качестве примера сравним табл. 1 и 5.2.1-3. Сортировка Бэтчера действует, как 8-, 4-, 2- и 1-сортировка, но сравнения не перекрываются. Поскольку в алгоритме Бэтчера, по сушеству, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортировкой со слиянием. Алгоритм М (Обменная сортировка со слиянием).
Записи В2,...,Н2е перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены: К2 « .. Кле Предполагается, что 211 > 2 (рис. 17). М1. (Начальная установка р.) Установить р +- 2е ', где 1 = (18Х) — наименьшее целое число, такое, что 2' > 211.
(Шаги М2 гМ5 будут выполняться с р = 2" ', 22 — е 1) 154 426 653 275 897 170 908 Г 061 087 503 509 154 ъ 426 беЗ 275 897 170 512 061 «, 503 087 509 426 653 275 897 е 170 512 154 503 Ф1 087 612 е09 «« 426 503 275 170 154 087 061 Рис. 17. Алгоритм М. М2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
