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

Алгоритмы поразрядной сортировки интерпретируют ключи как числа, представленные в системе счисления с основанием R, при различных значениях R (основание системы счисления — radix), и работают с отдельными цифрами этих чисел.

Применение поразрядной сортировки имеет одно ограничение: перед началом сортировки необходимо знать

· length – максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове),

· rang – количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).

На рисунке 9 представлен реализация сортировки.

Рисунок9

Код реализации массива:

· //элемент списка

· struct StringItem{

· const char*str; //указатель на строку

· StringItem*next;

· };

·

· //pList - начало списка указателей на строки

· //iDigit - разряд, по которому сортирует

· //возвращает указатель на первый элемент отсортированной последовательности

· StringItem*radix_sort_msd_for_string(StringItem*pList, unsigned intiDigit)

· {

· // количество вариантов значения одного разряда (char)

· const intiRange= 256;

·

· //массив bucket-ов (под-списков)

· StringItem*front[iRange];

· memset(front, 0, sizeof (front));

·

· StringItem**ppNextItem[iRange];

· for (inti= 0; i<iRange; i++)

· ppNextItem[i]=&front[i];

·

· //разбиваем список на bucket-ты, в зависимости от значения разряда

· while (pList)

· {

· StringItem*temp=pList;

· pList=pList->next;

·

· temp->next=NULL; //отключаем от списка

·

· unsigned char c = (unsigned char)temp->str[iDigit];

· *ppNextItem[c]=temp;

· ppNextItem[c]=&temp->next;

· }

·

· //строим выходной список

· StringItem*pResult= NULL;

· StringItem**ppNext=&pResult;

·

· //нулевой bucket возвращаем весь - он уже отсортирован

· *ppNext=front[0];

· while (*ppNext)

· ppNext=&((*ppNext)->next);

·

· for (inti= 1; i<iRange; i++)

· {

· //пустые - пропускаем

· if (!front[i])

· continue;

·

· if (front[i]->next== NULL) // с одним элементом - сразу добавляем

· *ppNext=front[i];

· else // остальные - на сортировку по следующему разряду

· *ppNext=radix_sort_msd_for_string(front[i], iDigit+ 1);

·

· while (*ppNext)

· ppNext=&((*ppNext)->next);

· }

·

· return pResult;}

Выводы:

1. Быстродействие по-умолчанию, пользователь может пробовать разные варианты.

2. Совместимость со стандартной библиотекой. В алгоритме используется один из основных шаблонов проектирования стандартной библиотеки — итератор.

3. Пользователь максимально отстранён от деталей реализации, но сохраняет контроль над происходящим. Пользователь не может «испортить» алгоритм, передать в функцию некорректные аргументы и т.п.

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