А = (min 1, ave N - /N/2 + 0(1), max N); (10)

В = (min 0, ave \(N - N), max (N - N)); (11)

C= (miniV-1, &ve 1{N - NlnN - (j + \п2 - 1)N) + 0{Vn),

max(N-N)). (12)

Bo всех случаях минимум достигается, когда исходная последовательность записей уже упорядочена, а максимум - когда записи расположены в обратном порядке. Таким образом, время работы для машины MIX равно 8А + 7В + 8С+1 = (min 8N + 1, ave 5.75N + 0(N log N), max T.SiV + 0.5iV + l).

Модификация метода пузырька. Мы потратили много усилий на анализ метода пузырька, и, хотя способы, применявшиеся при вычислениях, поучительны, результаты разочаровывают, поскольку они говорят о том, что метод пузырька вовсе не так уж хорош. По сравнению с простыми вставками (алгоритм 5.2. IS) метод пузырька описывается более сложной программой и требует примерно в 2 раза больше времени!

Можно предложить несколько путей улучшения метода пузырька. Например, на рис. 14 первое сравнение на проходе 4 лишнее, так же как и два первых сравнения на проходе 5 и три первых на проходах 6 и 7. Заметим, кроме того, что за один проход элемент не может переместиться более чем на одну позицию влево; так что если наименьший элемент вначале был крайним справа, то придется выполнить максимальное число сравнений. Это наводит на мысль о "шейкер-сортировке" когда последовательность записей просматривается попеременно в обоих направлениях (рис. 16). При таком подходе среднее число сравнений несколько сокращается. К. Э. Айверсон [см. К. Е. Iverson, А Programming Language (Wiley, 1962), 218-219] сделал интересное в этом отношении наблюдение: если j - такой индекс, что Rj и Rj+i не меняются местами на двух последовательных проходах в противоположных направлениях, то записи Rj и Rj+i должны занимать свои окончательные позиции и их можно исключить из последующих сравнений. Например, просматривая перестановку 432186975 слева направо, получаем 321468759; записи Л4 и Rs не поменялись местами. При просмотре последней перестановки справа налево R4 все еще меньше записи R5 (новой записи). Следовательно, можно сразу же сделать вывод о том, что записи Л4 и R5 могут и не участвовать ни в одном из последующих сравнений.

Однако ни одно из этих усовершенствований не приводит к лучшему варианту алгоритма, чем алгоритм сортировки методом простых вставок, а мы уже знаем, что даже он не годится при больших N. Другая идея состоит в том, чтобы избегать большинства обменов. Так как большая часть элементов во время обменов просто сдвигается на один шаг влево, можно было бы достичь того же эффекта, рассматривая массив иначе: сместив базу индексирования! Но полученный алгоритм не превосходит метода простого выбора (алгоритм 5.2.3S), о котором речь пойдет несколько ниже.

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

Рис. 16. Шейкер-сортировка.

Параллельная сортировка Бэтчера. Чтобы получить алгоритм обменной сортировки, время работы которого имеет порядок, меньший №, необходимо подобрать для сравнений пары несоседних ключей (Ki, Kj); иначе придется вьшолнить столько операций обмена записей, сколько инверсий имеется в исходной перестановке. Среднее число инверсий равно \(N - N). В 1964 году К. Э. Бэтчер [см. К. Е. Batcher Proc. AFIPS Spring Joint Computer Conference 32 (1968), 307-314] открыл интересный способ программирования последовательности сравнений, предназначенной для поиска возможных обменов. Его метод далеко не очевиден. В самом деле, обосновать его справедливость весьма сложно, поскольку выполняется относительно мало сравнений. Рассмотрим два доказательства: одно в этом разделе, а другое - в разделе 5.3.4.

Схема сортировки Бэтчера несколько напоминает сортировку Шелла, но сравнения выполняются по-новому, а потому цепочки операций обмена записей не возникает. В качестве примера сравним табл. 1 и 5.2.1-3. Сортировка Бэтчера действует, как 8-, 4-, 2- и 1-сортировка, но сравнения не перекрываются. Поскольку в алгоритме Бэтчера, по существу, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортировкой со слиянием.

Алгоритм М (Обменная сортировка со слиянием). Записи Л1,...,Лдг перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены: Ki < • • < АГдг. Предполагается, что N > 2 (рис. 17).

Ml. [Начальная установка р.] Установить р f- 2~\ где t = \lgN] - наименьшее целое число, такое, что 2 > N. (Шаги М2-М5 будут выполняться с р = 2*"", 2-...,1.)

М4. Сравнение/обмен Ri+i: Ri+a+i

р = 0

Рис. 17. Алгоритм М.

М2. [Начальная установка q, г, d.] Установить q +-2* , г +- О, d +- р.

МЗ. [Цикл по г.] Для всех г, таких, что 0<i<N-duiAp = r, выполнить шаг М4. Затем перейти к шагу М5. (Здесь через г Л р обозначена операция "поразрядное логическое И" над представлениями целых чисел i и р; все биты результата равны О, кроме тех битов, для которых в соответствующих разрядах г и р находятся 1. Так, 13 Л 21 = (1101)2 Л (10101)2 = (00101)2 = 5. К этому моменту d - нечетное кратное р (т. е. частное от деления d на р нечетно), а р - степень двойки, так что г t\p ф (i + d) Л р. Отсюда следует, что шаг М4 можно выполнять при всех нужных значениях i в любом порядке или даже одновременно.)

М4. [Сравнение/обмен Ri+i: Лг++ь] Если Ki+i > Ki+d+i, поменять местами записи Ri+i Ri+d+i-

М5. [Цикл по q.] Если q Ф р, установить d q - р, q q/2, г +- р и возвратиться к шагу МЗ.

Мб. [Цикл пор.] (К этому моменту перестановка KiKa-.- будет р-упорядочена.) Установить р +- [p/2J. Если р > О, возвратиться к шагу М2.

В табл. 1 этот метод проиллюстрирован при N = 16. Обратите внимание на то, что, по существу, алгоритм сортирует N элементов путем независимой сортировки подмассивов Л1,Дз,д5,... и R2,Ra,Rq, ..., после чего выполняются шаги М2-М5 при р = 1 для слияния двух рассортированных последовательностей.

Чтобы доказать, что магическая последовательность сравнений и/или обменов, описанная в алгоритме М, действительно позволяет рассортировать любую последовательность Ri R2 ... Rn, необходимо показать только, что в результате выполнения шагов М2-М5 при р = 1 будет слита любая 2-упорядоченная последовательность Ri R2 ... Rn С этой целью можно воспользоваться методом решеточных диаграмм из раздела 5.2.1 (см. рис. 11 на с. 106); каждая 2-упорядоченная перестановка множества {1,2,...,iV} соответствует на решетке единственному пути из вершины (0,0) к ([Л72], LiV/2j). На рис. 18, (а) показан пример при N = 16, соответствующий перестановке 13241051161371481591612. При р - 1, q := 2*-\ г = О, d = 1 на шаге МЗ выполняется сравнение (и, возможно, обмен) записей Ri:R2, Rs.Ri и т. д. Этой операции соответствует простое преобразование пути на решетке: