Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 30
Текст из файла (страница 30)
Если перед а; имеется больший элемент, то а; поменяется местами с наибольшим нз предшествующих элементов, так что Ьвч уменьшится на единицу. С другой стороны, если перед а; нет элемента, большего а;, то а, никогда не поменяется местами с большим элементом, так что 6, останется равным нулю. $ Итак, можно разобраться в том, что происходит в процессе сортировки методом пузырька, изучая последоватвльностывблиц инверсий между проходамн. Вот как выглядят, например, таблицы инверсий для рис. 14. 3183450403223210 Проход 1 2072340302112100 Проход 2 1001230201001000 Проход 3 ааоа12О1ОООООООО Теорема 1.
Пусть а! а»... а„- — перестановка множества (1,2,...,я), а Ь! Ьз... ܄— соответствующая табл»ша ипвсрс»»0. Если и результате очередного прохода прп сортнровкв методом пузырька (апгоритм В) перестановка а! аз... а„преобразуется в а»! а!»... а'„, то соответствующая таблица инверсий Ь' Ьз... 6'„получается яз Ь! Ьз... 6 в результате уиеньшснпя на едннпцу каждого ненулевого злелювта.
Поэтому, если Ь~ Ьт...܄— таблица инверсий исходной перестановки, то должны выполняться равенства (2) (3) (4) А = 1+ шах(Ь„Ь„.... „Ь„), В=Ь,+Ь,+" +Ь„, С =- с1 + «т + + сл, где су — значение ВООя0 — 1 перед началом у'-го прохода. Используя таблицы инверсий, запишем с = шах(Ь, +1 ~ Ь; > 1 — Ц вЂ” у (5) (см. упр. 5). Следовательно, в примере (1) А = 9, В = 41, С = 15+ 14+13+12+7+ 5+ 4+ 3+ 2 = 75.
Общее время сортировки на машине йХХ для случая, показанного на рис. 14, равно 960и. Распределение величины В (суммарного числа инверсий в сйучайной перестановке) нам уже хорошо известно; значит, остается проанализировать величины А и С. Вероятность того, что А < Ь, равна произведению 1/и! н числа таблиц инверсий, не содержащих компонент > Ь, а именно — Ь" ьй! при 1 < Ь < и. Следовательно, вероятность того, что потребуется ровно й проходов, равна Аь = — (Ь" ~И вЂ” (Ь вЂ” 1)" ьы(Ь вЂ” 1)!). 1 (6) и! Теперь можно вычислить среднее значение 2 ЙА».
Выполнив суммирование по частям, получаем и А,„, = и + 1 — 7 — = и + 1 — Р(и), и! ь=-о ~,(Ь) = (у+ Ь)! (т' — Ц"-'-' д 0 < Ь « -у (6) (см. упр, 6). Среднее значение с, в (о) равно Д к(у,(к) — Д(Ь вЂ” 1)))/ий Суммируя по частям, а затем по у, получаем формулу „.,=Г+') — — ', К, =("+,')- 1, К ..--*. 1<1<п о<~"<зйп Определить асимптотическое значение здесь не так просто, и мы вернемся к нему в конце этого раздела. Подводя итог анализу метода пузырька, запишем формулы, выведенные выше (а также ниже), следующим образом: где Р(п) — — функция, асимптотическое поведение которой, как следует из соотношения 1.2.11.3-(24), описывается формулой ~/хи~2 — 3 + 0(1/т/и ). Формула (7) была представлена без доказательства в работе Е.
Н. Рзг)епб, ХАСЫ 3 (1956), 150; доказательство в своей докторской диссертации привел Говард Б. Демут (Номвтб В. Оешвбй) (РЬ. О. ТЬез1з (91ап(огб Оштетвйу, ОстоЬег, 1956), 64-63). Стандартное отклонение величины А представлено в упр. 7. Проанализировать суммарное число сравнений С несколько сложнее, поэтому рассмотрим только среднее значение С„„,. Пусть ЯЬ) — число таких таблиц инверснйЬ~...Ь„(пфиксировано),чтопри1 < 1 < плибоЬ; < т' — 1,лнбоЬ,+1-.у < Ь; тогда А = (ппп 1, ате Х вЂ” т/иХ)2 + 0(1), шах Ф); В = (ппп О, ате 1(»ч — Ю), шах 1(Х» — Ж)); (19) (11) С = (»шп Ю вЂ” 1, ате»(»з!» -5!1п»т' — (7+!п2 — 1)Х) +0(~~Я), шах -'(Х» — »т')) . (12) Во всех случаях минимум достигается, когда исходная последовательность записей уже упорядочена, а максимум — когда записи расположены в обратном порядке.
Таким образом, время работы для машины М1Х равно 8А+ 7В+ 8С+ 1 = (ипп 8Х+ 1, ате 575Ф» + 0(»т !ой Х), пшх 75Х» + 05Х + 1). Модификация метода пузырька. Ыы потратили много усилий на анализ метода пузырька, и, хотя способы, применявшиеся при вычислениях, поучитечьны, результаты разочаровывают, поскольку они говорят о том., что метод пузырька вовсе не так уж хорош. По сравнению с простыми вставками (алгоритм 5.2.18) метод пузырька описывается более сложной программой и требует примерно в 2 раза больше времени! Можно предложить несколько путей улучшения метода пузырька. Например, на рис. 14 первое сравнение на проходе 4 лишнее, так же как и два первых сравнения на проходе 5 н три первых на проходах 6 н 7.
Заметим, кроме того, что за один проход элемент не может переместиться более чем иа одну позицию влево; так что если наименьший элемент вначале был крайним справа, то придется выполнить максимальное число сравнений. Это наводит на мысль о "шейкер-сортировке"„когда последовательность записей просматривается попеременно в обоих направлениях (рис.
16). Прн таком подходе среднее число сравнений несколько сокращается. К. Э. Айверсон !см. К. К. 1тегэоп, А Ргойтапип!пя Ьапяпайе (%йеу, 1962), 218-219) сделал интересное в этом отношении наблюдение; если у — такой индекс, что В» и Ву~» не меняются местами на двух последовательных проходах в противоположных направлениях, то записи В и В ~.» должны занимать свои окончательные позиции и их можно исключить из последующих сравнений.
Например, просматривая перестановку 4 3 2 1 8 6 9 7 5 слева направо, получаем 3 2 1 4 6 8 7 5 9„.записи Вя и Вь не поменялись местами. При просмотре последней перестановки справа налево В» все еще меньше записи В» (новой записи). Следовательно, можно сразу же сделать вывод о том., что записи В» и Вв могут и не участвовать ни в одном из последующих сравнений, Однако ни одно из этих усовершенствований не приводит к лучшему варианту алгоритма, чем авгоритм сортировки методом простых вставок, а мы уже знаем, что даже он не годится при больших Ф.
Другая идея состоит в том, чтобы избегать большинства обменов. Так как ббльшан часть элементов во время обменов просто сдвигается на один шаг влево, можно было бы достичь того же эффекш, рассматривая массив иначе: сместив базу индексирования! Но полученный алгоритм ие превосходит метода простого выбора (влгорнтм 5.2.38), о котором речь пойдет несколько пнже. Короче говоря, метод пузырька, кажется, не обладает никакими достоинствами, за которые его можно было бы порекомендовать, если не считать легко запоминающегося названия и интересных теоретических задач, к которым он приводит. 9ОВ В97 908 897 765 70З 677 653 703 ьь 765 612 509 154 ь, 426 653 275 897 а а 170 512 426 426 275 275 170 170 1э4 154 О87 ОВ7 061 061 170 154 О87 061 061 512 еФ' 087 ЬОЗ-эг 061 ~ 503 е, 087 Рис.
16. Шейкер-сортировка. Параллельная сортировка Вэтчера. Чтобы получить алгоритм обменной сортнровкн, время работы которого имеет порядок, меньший №, необходимо подобрать для сравнений пары несоседнит ключей (Кн К ); иначе придется выполнять столько операций обмена записей, сколько инверсий нмеется в исходной перестановке. Среднее число инверсий равно -'(Жэ — Х).
В 1964 году К. Э. Бэтчер [см. К. Е. Вагспег Ргос. АПРБ Бргшв .7шпс Сошритег СопГегепсе 32 (1968), 307-314) открыл интересный способ программирования последовательностн сравнений, предназначенной для поиска возможных обменов. Его метод далеко не очевиден. В самом деле, обосновать его справедливость весьма сложно, поскольку выполняется относнтельно мало сравнений. Рассмотрим два доказательства: одно в этом разделе, а другое— в разделе 5.3.4. Схема сортнровкн Бэтчера несколько н алом н наст сортировку Шелла, но сравнення выполняются по-новому, а потому цепочки операций обмена записей не возннкает.
В качестве примера сравним табл. 1 и 5.2.1-3. Сортировка Бзтчера действует, как 8-, 4-, 2- н 1-сортнровка, но сравнення не перекрываются. Поскольку в алгоритме Бзтчера, по существу, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортнровкой со слняннем. Алгоритм М (Обменная сртпироека со слиянием). Записи Вы...,Ян перекомпоновываются в пределах того же пространства в памяти. После завершения сортнровкн нх ключн будут упорядочены: К1 < < Кн. Предполагается, что К > 2 (рнс. 17).
М1. (Начальная установка р.] Установить р +- 2' ', где 1 = (18Ф) — нанменьшее целое число, такое, что 2' > Ж. (Шагн М2 — М5 будут выполняться с р = 2' ', 2ь-э 1 ) 703 765 677 612 ЬО9 154 э 426 653 275 В97 170 ; 9О84' 9ОВ 765 7ОЗ 677 612 509 426 а 653 в 275 ; 89742 170 512 г 154 503 ма 087 765 7ОЗ 677 612 509 426 ь 65З 275 ь1 512 170 ь 503 154 087 061 9ОВ 897 765 703 677 612 509 653 г 426 512 275 503 612 509ьь 512 426 ь, ЬОЗ 275 170 154 087 О61 908 908 897 В97 765 765 703 703 677 677 653 653 612 612 512 512 509 509 503 503 Рис. 17. Алгоритм М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
