Алгоритмы сортировки.

Распределяющая сортировка.

Перевод Кантор И.

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

I. Составим таблицу распределения. В ней будет 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;

   }

Для того, чтобы понять, что алгоритм действительно работает, советую взять m=10 и некоторый небольшой набор чисел, а затем провести операции вручную на листе бумаги.

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

Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).

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

Причем большее быстродействие всегда можно 'купить' за счет памяти, увеличив m ( например, для чисел взяв его не 256, а m=65536 ), и, таким образом, уменьшив число проходов.

Реализация на 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';
}
   

Вверх по странице, к оглавлению и навигации.