2015-05-10
649
Рассматриваемый ниже алгоритм существенно отличается от описанных ранее.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...
До сортировки необходимо знать два параметра: k и m, где
- k - количество разрядов в самом длинном ключе
- m - разрядность данных: количество возможных значений разряда ключа
При сортировке русских слов m = 33, так как буква может принимать не более 33 значений. Если в самом длинном слове 10 букв, k = 10.
Аналогично, для для шестнадцатиричных чисел m=16, если в качестве разряда брать цифру, и m=256, если использовать побайтовое деление.
Эти параметры нельзя изменять в процессе работы алгоритма. В этом - еще одно отличие метода от вышеописанных.
Поразрядная сортировка для списков
Предположим, что элементы линейного списка L есть k-разрядные десятичные числа, разрядность максимального числа известна заранее. Обозначим d(j,n) - j-ю справа цифра числа n, которую можно выразить как
d(j,n) = [ n / 10j-1 ] % 10
Пусть L0, L1,..., L9 - вспомогательные списки (карманы), вначале пустые. Поразрядная сортировка состоит из двух процессов, называемых распределение и сборка и выполняемых для j=1,2,...,k.
Фаза распределения разносит элементы L по карманам: элементы li списка L последовательно добавляются в списки Lm, где m = d(j, li). Таким образом получаем десять списков, в каждом из которых j-тые разряды чисел одинаковы и равны m.
Фаза сборки состоит в объединении списков L0, L1,..., L9 в общий список
L = L0 => L1 => L2 =>... => L9
Рассмотрим пример работы алгоритма на входном списке
0 => 8 => 12 => 56 => 7 => 26 => 44 => 97 => 2 => 37 => 4 => 3 => 3 => 45 => 10.
Максимальное число содержит две цифры, значит, разрядность данных k=2.
Первый проход, j=1.
Распределение по первой справа цифре:
L0: 0 => 10 // все числа с первой справа цифрой 0
L1: пусто
L2: 12 => 2
L3: 3 => 3
L4: 44 => 4
L5: 45
L6: 56 => 26
L7: 7 => 97 => 37
L8: 8
L9: пусто // все числа с первой справа цифрой 9
Cборка:
соединяем списки Li один за другим
L: 0 => 10 => 12 => 2 => 3 => 3 => 44 => 4 => 45 => 56 => 26 => 7 => 97 => 37 => 8
Второй проход, j=2.
Распределение по второй справа цифре:
L0: 0 => 2 => 3 => 3 => 4 => 7 => 8
L1: 10 => 12
L2: 26
L3: 37
L4: 44 => 45
L5: 56
L6: пусто
L7: пусто
L8: пусто
L9: 97
Cборка:
соединяем списки Li один за другим
L: 0 => 2 => 3 => 3 => 4 => 7 => 8 => 10 => 12 => 26 => 37 => 44 => 45 => 56 => 97
Число используемых карманов - количество возможных значений элемента списка.
Сортировку можно организовать так, чтобы не использовать дополнительной памяти для карманов, т.е элементы списка не перемещать, а с помощью перестановки указателей присоединять их к тому или иному карману.
В представленной ниже программе функция radix_list реализует поразрядную сортировку связанного линейного списка (указатель l), в котором содержатся t-разрядные десятичные положительные числа, без использования дополнительной памяти;
Параметры head[i], tail[i] указывают соответственно на первый и на последний элементы кармана Li. При этом сами карманы являются "виртуальными", память под них не выделяется.
typedef struct slist_ { long val; struct slist_ *next; } slist; // функция сортировки возвращает указатель на начало отсортированного списка slist *radix_list(slist *l, int t) { // t - разрядность (максимальная длина числа) int i, j, d, m=1; slist *temp, *out, *head[10], *tail[10]; out=l; for (j=1; j<=t; j++) { for (i=0; i<=9; i++) head[i] = (tail[i]=NULL); while (l!= NULL) { d = ((int)(l->val/m))%(int)10; temp = tail[d]; if (head[d]==NULL) head[d] = l; else temp->next = l; temp = tail[d] = l; l = l->next; temp->next = NULL; } for (i=0; i<=9; i++) if (head[i]!= NULL) break; l = head[i]; temp = tail[i]; for (d=i+1; d<=9; d++) { if (head[d]!= NULL) { temp->next = head[d]; temp = tail[d]; } } m*=10; } return (out);}
