5. Распределяющая сортировка Эта группа методов использует стратегию, прямо противоположную методам слияния. Ключи K[i] элементов файла рассматриваются в этом алгоритме как некоторые последовательности из s символов в известном алфавите K=(A1,A2,A3,...,As). Например, такой порядок используется для расположения слов в словаре. Если множество слов упорядочить сначала по правой букве, затем, не меняя порядка по правой букве, упорядочить их по следующей букве и т.д. до конца слова, то слова будут расположены в лексикографическом порядке. Можно начинать выбор букв как с конца, так и с начала слов. В процессе упорядочивания по букве множество слов разбивается на подмножества с одинаковыми зна- чениями данной буквы, а затем подмножества снова объединяются в одно множество в порядке, соответствующем алфавитному порядку для значе- ний этой буквы. Распределение множества по подмножествам и дало наз- вание этой группы методов. Алгоритм имеет следующий вид. Функция АДР(переменная) возвращает указатель на переменную. Функция ЭЛЕМ(указатель) позволяет выполнять операции над элементом файла,на который указывает аргумент функции. Подмножества, отсортированные по одной букве ключа, хранятся в виде М очередей, где М - количество возможных значений каждой буквы. Для каждой из М очередей существует два массива указателей: BOTM[0] ... BOTM[N] и TOP[0] ... TOP[M], указывающие соответственно на начала и концы очередей-подмножеств.BOTM[0] указывает в конце алгоритма на начало объединенного списка. Каждый элемент файла имеет поле ключа K[i] и поле связи L[i], указывающее на следующий элемент в отсорти- рованном файле. Символом @ обозначен пустой указатель. Его конкрет- ное значение может быть выбрано произвольно и использоваться в алго- ритме только в этом смысле. p=АДР(K[N]);j=N; ┌──────────────── for k=1 to s ───────────────────────────────────────┐ │ ┌───────────────────┐ │ │ for i=0 to M │TOP[i]=АДР(BOTM[i];│ │ │ │BOTM[i]=@; │ │ │ └───────────────────┘ │ │ ║ │ │ ╔═>═╬═════════════════════════════════════════<══════════════════╗ │ │ ║ i=(k-я младшая буква ключа, на который указывает переменная p) ║ │ │ ║ ║ │ │ ║ L[ЭЛЕМ(TOP[i])]=p; ║ │ │ ║ TOP[i]=p; ║ │ │ ║ if(k=1) ║ │ │ ║ then ║ else ║ │ │ ║ ╔══<══╩═════════════════>═════╗ ║ │ │ ║ j=j-1; if(p ╪ @) p=L[ЭЛЕМ(p)]; ══>════╝ │ │ ║ if(j ╪ 0) p=АДР(K[j];═>╗ else ═══>╗ │ │ ╚══<══════════════════════╝ ║ │ │ else ════════════════>═══╦═══<═══════════╝ │ │ ║ │ │ p=TOP[0] │ │ ┌─for i=1 to M-1─────┐ │ │ │ if(BOTM[i]=@)═══>══╡ │ │ │ L[ЭЛЕМ(p)]=BOTM[i] │ │ │ │ p=TOP[i] │ │ │ └────────────────────┘ │ │ L[ЭЛЕМ(p)]=@ │ │ p=BOTM[0] │ └─────────────────────────────────────────────────────────────────────┘ Работу алгоритма проиллюстрируем на примере файла из 16 элемен- тов, сортировка будет проводится по цифрам ключей, начиная с млад- шей. Исходный файл: 703 765 677 612 509 154 426 653 275 897 170 908 61 512 87 503 Файл после 1-го прохода (k=1) TOP[0] TOP[1] TOP[2] TOP[3] TOP[4] TOP[5] TOP[6] TOP[7] TOP[8] TOP[9] ┌─┴──┐ ┌──┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴┐ ┌─┴─┐ ┌─┴─┐ │170 │ │ 61 │ │512│ │503│ │154│ │275│ │426│ │87│ │908│ │509│ └─┬──┘ └──┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬┘ └─┬─┘ └─┬─┘ │ │ ┌─┴─┐ ┌─┴─┐ │ ┌─┴─┐ │ ┌─┴─┐ │ │ │ │ │612│ │653│ │ │765│ │ │897│ │ │ │ │ └─┬─┘ └─┬─┘ │ └─┬─┘ │ └─┬─┘ │ │ │ │ │ ┌─┴─┐ │ │ │ ┌─┴─┐ │ │ │ │ │ │703│ │ │ │ │677│ │ │ │ │ │ └─┬─┘ │ │ │ └─┬─┘ │ │ │ │ │ │ │ │ │ │ │ │ BOTM[0] │ BOTM[2] │ BOTM[4] BOTM[6] BOTM[8] BOTM[1] BOTM[3] BOTM[5] BOTM[7] BOTM[9] Файл после 2-го прохода (k=2) TOP[0] TOP[1] TOP[2] TOP[3] TOP[4] TOP[5] TOP[6] TOP[7] TOP[8] TOP[9] ┌──┴─┐ ┌──┴─┐ ┌─┴─┐ │ │ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ │ 509│ │ 512│ │426│ │ │ │154│ │765│ │677│ │ 87│ │897│ └──┬─┘ └──┬─┘ └─┬─┘ │ │ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ ┌──┴─┐ │ │ │ │ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ │ │ │ 908│ ┌──┴─┐ │ │ │ │653│ │ 61│ │275│ │ │ └──┬─┘ │ 612│ │ │ │ └─┬─┘ └─┬─┘ └─┬─┘ │ │ ┌──┴─┐ └──┬─┘ │ │ │ │ │ ┌─┴─┐ │ │ │ 503│ │ │ │ │ │ │ │170│ │ │ └──┬─┘ │ │ │ │ │ │ └─┬─┘ │ │ ┌──┴─┐ │ │ │ │ │ │ │ │ │ │ 703│ │ │ │ │ │ │ │ │ │ └──┬─┘ │ │ │ │ │ │ │ │ │ BOTM[0] │ BOTM[2] │ BOTM[4] BOTM[6] BOTM[8] BOTM[1] BOTM[3] BOTM[5] BOTM[7] BOTM[9] Файл после 3-го прохода (k=3) TOP[0] TOP[1] TOP[2] TOP[3] TOP[4] TOP[5] TOP[6] TOP[7] TOP[8] TOP[9] ┌──┴─┐ ┌──┴─┐ ┌─┴─┐ │ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ │ 87 │ │ 170│ │275│ │ │426│ │512│ │677│ │765│ │897│ │908│ └──┬─┘ └──┬─┘ └─┬─┘ │ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ ┌──┴─┐ │ │ │ │ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ │ │ │ 61│ ┌──┴─┐ │ │ │ │509│ │653│ │703│ │ │ └──┬─┘ │ 154│ │ │ │ └─┬─┘ └─┬─┘ └─┬─┘ │ │ │ └──┬─┘ │ │ │ │ │ │ │ │ │ │ │ │ │ ┌─┴─┐ ┌─┴─┐ │ │ │ │ │ │ │ │ │503│ │612│ │ │ │ │ │ │ │ │ └─┬─┘ └─┬─┘ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ BOTM[0] │ BOTM[2] │ BOTM[4] BOTM[6] BOTM[8] BOTM[1] BOTM[3] BOTM[5] BOTM[7] BOTM[9] После 3-го прохода видно, что сцепление всех очередей от 0 до 9 дает отсортированный файл. Время работы алгоритма t примерно оценивается формулой: t=a*N + b где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма.