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

Рассматриваемый ниже алгоритм существенно отличается от описанных ранее.

Во-первых, он совсем не использует сравнений сортируемых элементов.

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

До сортировки необходимо знать два параметра: 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 / 10^j-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);

}

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

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

Сортировка подсчетом

Пусть у нас есть массив source из n десятичных цифр ( m = 10 ).
Например, source[7] = { 7, 9, 8, 5, 4, 7, 7 }, n=7. Здесь положим const k=1.

1. Создать массив count из m элементов(счетчиков).
2. Присвоить count[i] количество элементов source, равных i. Для этого:

1. проинициализовать count[] нулями,
2. пройти по source от начала до конца, для каждого числа увеличивая элемент count с соответствующим номером.

c. for( i=0; i<n; i++) count [ source[i] ]++

В нашем примере count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }

1. Присвоить count[i] значение, равное сумме всех элементов до данного:
   count[i] = count[0]+count[1]+...count[i-1].
   В нашем примере count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }
   Эта сумма является количеством чисел исходного массива, меньших i.
2. Произвести окончательную расстановку.

Для каждого числа source[i] мы знаем, сколько чисел меньше него - это значение хранится в count[ source[i] ]. Таким образом, нам известно окончательное место числа в упорядоченном массиве: если есть K чисел меньше данного, то оно должно стоять на на позиции K+1.
Осуществляем проход по массиву source слева направо, одновременно заполняя выходной массив dest:

for ( i=0; i<n; i++ ) { c = source[i]; dest[ count[c] ] = c; count[c]++; // для повторяющихся чисел }

Таким образом, число c=source[i] ставится на место count[c]. На этот случай, если числа повторяются в массиве, предусмотрен оператор count[c]++, который увеличивает значение позиции для следующего числа c, если таковое будет.

Циклы занимают (n + m) времени. Столько же требуется памяти.

Итак, мы научились за (n + m) сортировать цифры. А от цифр до строк и чисел - 1 шаг. Пусть у нас в каждом ключе k цифр ( m = 10 ). Аналогично случаю со списками отсортируем их в несколько проходов от младшего разряда к старшему.

Общее количество операций, таким образом, ( k(n+m) ), при используемой дополнительно памяти (n+m). Эта схема допускает небольшую оптимизацию. Заметим, что сортировка по каждому байту состоит из 2 проходов по всему массиву: на первом шаге и на четвертом. Однако, можно создать сразу все массивы count[] (по одному на каждую позицию) за один проход. Неважно, как расположены числа - счетчики не меняются, поэтому это изменение корректно.
Таким образом, первый шаг будет выполняться один раз за всю сортировку, а значит, общее количество проходов изменится с 2k на k+1.