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


     Пусть имеем k байт в каждом ключе ( хотя, за единицу измерения вполне можно принять и что-либо другое. В том числе и 2 байта ; - ) ).
     Разрядность данных - m.

     Данный алгоритм весьма прост. Для начала, пусть у нас есть массив из n элементов по одному байту в каждом. Тогда m = 256.

     I. Составим таблицу распределения. D ней будет m ( = 256 ) значений и заполняться она будет так:

for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;

     Здесь source - массив сортируемых ключей. Для массива source = { 7, 9, 8, 5, 4, 7, 7 } и m = 9 , будем иметь distr = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 } то есть i-ый элемент distr[] - количество ключей со значением i.

     Заполним таблицу индексов:

int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];

     В index[i] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i. Например, index[8] = 5 : 4, 5, 7, 7, 7, 8.

     А теперь заполняем новосозданный массив sorted размера n:

for ( i = 0; i < n ; i++ )
     {
      sorted[ index[ source[i] ] ]=source[i];
 // попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
      index[ source[i] ] = index[ source[i] ] +1;
     }

     Итак, мы научились за O ( n ) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

     Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).
сначала они в беспорядке:
523
153
088
554
235
сортируем по младшему разряду:
523
153
554
235
088
на один выше:
523
235
153
554
088
и еще раз:
088
153
235
523
554


     Ну вот мы и отсортировали за O ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой сортировки' !

Реализация на C++ для long int'ов


#include <iostream.h>

#include < stdlib.h>

#include < string.h>



void radix (int byte, long N, long *source, long *dest)

{

 long count[256];

 long index[256];

 memset (count, 0, sizeof (count));

 for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;

 index[0]=0;

 for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];

 for(i=0;i<N;i++) dest[index[((source[i])>>(byte*8))&0xff]++]=source[i];

}



void radixsort (long *source, long *temp, long N)

{

 radix (0, N, source, temp);

 radix (1, N, temp, source);

 radix (2, N, source, temp);

 radix (3, N, temp, source);

}



void make_random (long *data, long N)

{

 for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);

}



long data[10000];

long temp[10000];



void main (void)

{

 make_random(data, 10000);

 radixsort (data, temp, 10000);

 for ( int i=0; i<100; i++ ) cout << data[i] << '\n';

}


Вверх
вверх