061 087/503f 512908

154 170 275 426 509 612 653

897 765

Рис. 13. Пример схемы Уилера для вставок в дерево.

нальный метод Уилера [см. А. S. Douglas, Сотр. J. 2 (1959), 5] предполагал использование довольно замысловатой комбинации последовательной и связной памяти с узлами переменного размера; для тех шестнадцати чисел, которые используются в качестве примера неупорядоченной последовательности, таким способом было бы сформировано дерево, показанное па рис. 13. Аналогичную, но более простую схему со вставками в бинарную древовидную структуру изобрел К. М. Бернерс-Ли (С. М. Berners-Lee) примерно в 1958 году [см. Сотр. J. 3 (I960), 174, 184]. Поскольку сам метод с использованием бинарного дерева и его модификации очень важны как для сортировки, так и для поиска, его подробное обсуждение мы отложим до раздела 6.2.2 главы 6.

Еще один путь улучшения метода простых вставок - попытаться вставлять несколько записей одновременно. Если, например, имеется массив из 1 ООО элементов и 998 из них уже рассортированы, то алгоритм S выполнит enie два просмотра массива (вставив сначала Л999, а потом Люоо)- Очевидно, можно сэкономить время, если сначала сравнить ключи Кддд и Кшо и выяснить, какой из них больше, а затем вставить оба ключа за один просмотр массива. Комбинированная операция такого рода требует около iV сравнений и перезаписей (см. упр. 3.4.2-5) вместо двух просмотров, примерно по сравнений и перезаписей каждый.

Иначе говоря, обычно полезно "группировать" операции, которые требуют длительного поиска, чтобы можно было выполнить несколько операций сразу. Если довести эту идею до ее естественного завершения, то будет заново открыта сортировка посредством слияния, настолько важная, что ей посвящен отдельный раздел (5.2.4).

Сортировка с вычислением адреса. Ну уж теперь-то, несомненно, исчерпаны все возможные способы усовершенствования .методов простых вставок! Но давайте подумаем еще. Представьте себе, что вам поручили расставить несколько дюжин книг на полке по фамилиям авторов, причем книги берутся с по.:-л в случайном порядке. Ставя книгу на полку, вы, естественно, попробуете прикинуть, где примерно она будет, в конце концов, стоять, и таким образом потенциально сократите число необходимых в будущем сравнений и перестановок. Эффективность процесса повысится, если на полке будет немного больше места, чем это абсолютно необходимо. Такой метод для реализации компьютерной сортировки впервые предложили Исаак (Isaac) и Синглтон (Singleton) [см. JACM 3 (1956), 169-174]; он получил дальнейшее развитие в работе Тартера (Tarter) и Кронмэла (Kronmal) [см. Ргос. АСМ Nat 7 Conf. 21 (1966), 331-337].

Сортировка с вычислением адреса обычно требует дополнительного пространства в памяти либо для того, чтобы оставить достаточно свободного места и не делать много лишних перемещений, либо для хранения вспомогательных таблиц, которые позволяли бы учитывать неравномерность распределения ключей. (См. сортировку методом подсчета распределения (алгоритм 5.2D), которая является разновидностью сортировки с вычислением адреса.) Дополнительное пространство будет, по-видимому, использоваться наилучшим образом, если отвести его для полей связи, как в методе вставок в список. К тому же отпадает необходимость в выделении отдельных областей для ввода и вывода; все операции можно выполнить в одной и той же области памяти. Основная цель - так обобщить метод вставок в список, чтобы работать не с одним списком, а с несколькими. Каждый список содержит ключи из определенного диапазона. Мы делаем важное предположение о том, что ключи распределены довольно равномерно и не скапливаются хаотически в отдельных областях значений. Множество всех возможных значений -ключей разбивается на М частей, и предполагается, что данный ключ попадает в данное подмножество с вероятностью 1/М. Отводим дополнительную память для головных элементов М списков, а каждый список обрабатываем, как при простых вставках в список.

Нет необходимости приводить здесь этот алгоритм со всеми подробностями. Достаточно вначале установить все головные элементы списков равными Л, для каждого вновь поступившего элемента предварительно решить, в какое из М подмножеств он попадает, после чего вставить его в соответствующий список, как в алгоритме L.

Чтобы проиллюстрировать этот метод в действии, предположим, что наши 16 ключей разделены на М = 4 поддиапазона: 0-249, 250-499, 500-749, 750-999. В процессе сортировки по мере того, как будут вставляться ключи Ki, К2, ..., Kiq, получатся следующие конфигурации.

Пришли Пришли Пришли Всего

4 элемента 8 элементов 12 элементов

Список 1: 061,087 061,087,170 061,087,154,170 061,087,154,170

Список 2: 275 275,426 275,426

Список 3: 503,512 503,512 503,509,512,653 503,509,512,612,653,677,703

Список 4: 897,908 897,908 765,897,908

(Программа М, описанная ниже, в действительности вставляет ключи в обратном порядке, Kie, К2, Ki, но окончательный результат тот же.) Благодаря организации в памяти структуры связных списков не возникает проблем, связанных с выделением памяти при изменении длины списка. При желании в конце выполнения программы все списки можно объединить в один (см. упр. 35).

Программа М {Вставка в несколько списков). При разработке этой программы сделано такое же предположение, как и в программе L, но ключи должны быть неотрицательными, т. е.

0<Kj < (BYTESIZE)

В программе этот диапазон делится на М равных частей посредством умножения каждого ключа на соответствующую константу. Головные элементы списков хранятся в ячейках от HEAD+1 до HEAD+M.

HEADCp] <- A.

M>p>l. j<-N.

rA <- [M • /fj/BYTESIZEJ. rI4 <- rA.

g <-LOC(HEAD[rA]). К <-Kj.

Переход на установку p.

Переход на вставку, если К <Кр. q<-p.

p<-LINK(g).

Переход, если не конец списка. LINK(g) <- LOC(Rj). LINK(LOC(fij)) <-р.

N>j>l. I

Эта программа написана для любого значения М, но лучше зафиксировать М, положив его равным некоторому приемлемому значению; можно, например, псшо-жить М = BYTES IZE, тогда головные элементы списков можно очистить с помощью одной-единственной команды MOVE, а последовательность команд 08-11, реализующих умножение, заменить единственной командой LD3 INPUT, 1(1:1). Наиболее заметное отличие программы М от программы L состоит в том, что в программе М нужно принимать во внимание и возможность образования пустого списка, когда не надо делать сравнений.

Сколько же времени мы экономим, имея М списков вместо одного? Общее время выполнения программы М равно 7J5+31iV -ЗЛ+4М+2 машинных циклов, где М - число списков, N - число сортируемых записей, Аи В равны соответственно числу правосторонних максимумов и числу инверсий среди ключей, принадлежащих каждому списку. (Анализируя этот алгоритм, в отличие от всех других в данном разделе, мы включаем в подсчет А и крайний справа элемент непустой перестановки, а не игнорируем его.) Мы уже проанализировали величины Аа В при М = 1, когда их средние значения оказались равными соответственно Hjm и j (). Согласно предположению о распределении ключей вероятность того, что данный список в конце сортировки будет содержать ровно п элементов, есть "биномиальная" вероятность

;еличин А и В в oi

Поэтому средние значения величин А и В в общем случае равны

.N-n

(14)