Сортировка методом распределения

 

Данный тип сортировки по своей сути является обратным слиянию. Данный тип сортировки начал широко использоваться со времен машин с перфокарточным оборудованием. Она общеизвестна под названиями "поразрядная сортировка", "карманная сортировка" (bucket sorting) и "цифровая сортировка" (digital sorting), поиск базируется на анализе цифр ключей.

 

Поразрядная сортировка

 

Отличительными особенностями данного способа сортировки являются:

 

1. Отсутствие сравнений сортируемых элементов.

2. Ключ, по которому происходит сортировка, делится на части, разряды ключа. Например, слово можно разделить по буквам, а число - по цифрам...

 

До сортировки необходимо знать два параметра: k и m, где

 

k - количество разрядов в самом длинном ключе

m - разрядность данных: количество возможных значений разряда ключа

 

Эти параметры нельзя изменять в процессе работы алгоритма.

 

Поразрядная сортировка для списков

 

Предполагается, что элементы линейного списка L есть k-разрядные десятичные числа, разрядность максимального числа известна заранее. Через d(j,n) обозначается j-я справа цифра числа n

 

Пусть L₀, L₁,..., L₉ - вспомогательные списки (карманы), которые вначале пусты. Поразрядная сортировка состоит из двух процессов, называемых распределение и сборка и выполняемых для j=1,2,...,k.

 

Фаза распределения разносит элементы L по карманам: элементы l_i списка L последовательно добавляются в списки L_m, где m = d(j, l_i). Таким образом получается десять списков, в каждом из которых j-тые разряды чисел одинаковы и равны m.

 

Фаза сборки состоит в объединении списков L₀, L₁,..., L₉ в общий список

L = L₀ => L₁ => L₂ =>... => L₉

 

Поразрядная сортировка растет линейным образом по n, так как k,m - константы.

Данный тип сортировки является наиболее эффективным для компьютеров с магистральной архитектурой. Эти машины имеют несколько арифметических устройств и схему "опережения" так что обращения к памяти и вычисления могут в значительной степени совмещаться во времени.

2.2 Внешняя сортировка [19]

Будем понимать под "внешней" сортировкой сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы их можно было целиком переместить в основную память и применить один из рассмотренных выше методов внутренней сортировки. Наиболее часто внешняя сортировка применяется в системах управления базами данных. Практически все методы внешней сортировки, излагаемые в настоящем пособии, основаны на слиянии.

Прямое слияние

Предположим, что имеется последовательный файл A, состоящий из записей a₁, a₂,..., a_n (для простоты предполагается, что n представляет собой степень числа 2). Будем считать, что каждая запись состоит ровно из одного элемента, представляющего собой ключ сортировки. Для сортировки используются два вспомогательных файла B и C, размер каждого из них будет равен n/2.

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение содержимого файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и нечетные записи пишутся в файл B, а четные - в файл C (начальное распределение). Начальное слияние производится над парами (a₁, a₂), (a₃, a₄),..., (a_n-1, a_n), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей. Заметим, что для выполнения внешней сортировки методом прямого слияния в основной памяти требуется расположить всего лишь две переменные - для размещения очередных записей из файлов B и C. Файлы A, B и C будут O(log n) раз прочитаны и столько же раз записаны.

Естественное слияние

При использовании метода прямого слияния не принимается во внимание то, что исходный файл может быть частично отсортированным, т.е. содержать упорядоченные подпоследовательности записей. Серией называется подпоследовательность записей a_i, a_i+1,..., a_j такая, что a_k£a_k+1 для всех i £ k £ j, a_i < a_i-1 и a_j > a_j+1. Метод естественного слияния основывается на распознавании серий при распределении и их использовании при последующем слиянии.

Как и в случае прямого слияния, сортировка выполняется за несколько шагов, в каждом из которых сначала выполняется распределение файла A по файлам B и C, а потом слияние B и C в файл A. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C, вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток файла целиком копируется в конец файла A. Процесс завершается, когда в файле A остается только одна серия.