Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Сортировка /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Поразрядная сортировка - Программирование от RIN.RU
Поразрядная сортировка

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


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


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


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




Вперед  >>>
 1  2 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь