Delphi World - Байтовая, Цифровая, Радиксная или Распределяющая сортировка
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Байтовая, Цифровая, Радиксная или Распределяющая сортировка

A: Kantor Ilia
  
  Пусть имеем максимум по k байт в каждом ключе ( хотя за элемент
 сортировки вполне можно принять и что-либо другое, например слово -
 двойной байт, или буквы, если сортируются строки). k должно быть
 известно заранее, до сортировки.

 Разрядность данных ( количество возможных значений элементов ) - m,
также должна быть известна заранее и постоянна.
                                                               
  Если мы сортируем слова, то элемент сортировки - буква. m = 33.
 Если в самом длинном слове 10 букв, k = 10.

 Обычно мы будем сортировать данные по ключам из k байт, m=256.

----------------------------------------------------------------------
  Пусть у нас есть массив source из n элементов по одному байту в каждом.

 Для примера можете выписать на листочек массив 
 source[1..7] = { 7,9,8,5,4,7,7 }, и проделать с ним все операции,
 имея в виду m=9. n здесь, очевидно, равно 7.
                                                            
     I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и
заполняться она будет так:

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

  Для нашего примера будем иметь 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. 
     Hапример, 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                523                523         088
           153                153                235         153
           088                554                153         235
           554                235                554         523
           235                088                088         554
                               /|\               /|\        /|\
                                |                 |          |								
    Вот мы и отсортировали массив за O(kn) шагов. Если количество
возможных различных ключей ненамного превышает общее их число, то
поразрядная сортировка оказывается гораздо быстрее даже 'быстрой
сортировки' !

     Распределяющая сортировка, требует O(n) дополнительной памяти.

 Пример(учебный) реализации radixsort на Си++ для long int'ов.
 
 #include <iostream.h>
 #include <stdlib.h>
 #include <string.h>

 void radix (int byte, long N, long *source, long *dest)
 {
  // *source - входной массив,
  // *dest - отсортированный.
  long count[256];    // вообще говоря, можно обойтись 
  long index[256];    // одним массивом count[]
  
  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)
 {
  // Сортируем по всем 4 разрядам
  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';
 }
 
 Примечания.
 
1.  К сожалению, или к счастью, единица информации в современной 
 технике способна принимать лишь 2 значения: 1 и 0.
  А значит, любые компьютерные данные тоже могут принимать 
 ограниченное количество значений, так как состоят из некоторого 
 числа битов ;-)). 
  Таким образом, распределяющая сортировка потенциально применима
 где угодно. Другое дело, что если разрядность данных большая 
 по сравнению с общим количеством элементов, то скорость работы
 оставит желать много лучшего.

2. Алгоритм, описанный выше, очевидно, требует O(n) памяти.
Существует похожий алгоритм, использующий лишь O(logn).
  Модифицированная Radix Sort:
Будем сортировать по каждой позиции символа 'на месте', начиная справа:
сначала сортируем по первой позиции, затем к каждой части массива,
относящейся к одному и тому же значению, рекурсивно 
применяем ту же процедуру и т.д.

 Этот вариант называется 'Radix exchange sort' и 
представляет собой скорее разновидность QuickSort. 
 Hа мой взгляд, она объединяет больше плохих черт обоих методов,
нежели хороших, но вполне может пригодиться в какой-то ситуации.

>  Существует вариант распределяющей сортировки для списков,
> каждый элемент которых принимает конечное множество значений.
> Он даже проще в реализации, понимании и использовании.

Предположим, что элементы линейного списка В есть Т-разрядные
положительные десятичные числа D(j,n) - j-я справа цифра в десятичном 
числе n>=0, т.е. D(j,n)=floor(n/m)%10, где m=10^(j-1).
 (floor - округление в меньшую сторону)
 Пусть В0,В1,...,В9 - вспомогательные списки (карманы), вначале пустые. 
Для реализации распределяющей сортировки выполняется процедура, 
состоящая из двух процессов, называемых распределение и сборка 
для j=1,2,...,T. 

PАСПРЕДЕЛЕHИЕ 
заключается в том, что элемент Кi (i=1,N) из В добавляется как 
последний в список Bm, где m=D(j,Ki), и таким образом получаем 
десять списков, в каждом из которых j-тые разряды чисел одинаковы и 
равны m. 

СБОРКА 
объединяет списки В0,В1,...,В9 в этом же порядке, 
образуя один список В.
 
> Число карманов - количество возможных значений элемента списка.

Исходный список можно сделать односвязный, а сортировку организовать так,
чтобы для карманов В0,В1,...,В9 не использовать дополнительной памяти, т.е
элементы списка не перемещать, а с помощью перестановки указателей 
присоединять их к тому или иному карману. 

В представленной ниже программе функция pocket реализует распределяющую 
сортировку связанного линейного списка (указатель q), в котором содержатся
Т-разрядные десятичные положительные числа, без использования 
дополнительной памяти;
в функции a[i], b[i] указывают соответственно на первый и на последний 
элементы кармана Bi. 

/*  распределяющая  сортировка  списка    */
#include <stdlib.h>
#include <stdio.h>
	 
typedef struct SP1_ { 
   long val;
   struct SP1_ *next; 
} SP1;

 /*    функция сортировки возвращает указатель на начало
        отсортированного списка      */
SP1 *pocket(SP1 *q,int t) {
    /* t - разрядность (максимальная длина числа) */
   int i,j,k,m=1;
   SP1 *r, *gg, *a[10], *b[10];
   gg=q;
   for(j=1;j<=t;j++) { 
       for(i=0;i<=9;i++) a[i]=(b[i]=NULL);
       while(q!=NULL) {
           k=((int)(q->val/m))%(int)10;
           r=b[k];
           if (a[k]==NULL) a[k]=q; else r->next=q;
           r=b[k]=q;
           q=q->next;
           r->next=NULL;
       }
       for(i=0;i<=9;i++) if (a[i]!=NULL) break;
       q=a[i];
       r=b[i];
       for(k=i+1;k<=9;k++)
           if(a[k]!=NULL) { 
	       r->next=a[k];
               r=b[k];
           }
       m=m*10;
       }
   return (gg);
}

   /* Тестовая программа */	 
void main() {
   int i;
   SP1 *q, *r;
   /* Это будем сортировать */
   long a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };

   q=(SP1 *)malloc(sizeof(SP1));
   q->val=a[0];
   r=q;
   for(i=1;i<14;i++) {     /*  формирование списка  */
         r->next=(SP1 *)malloc(sizeof(SP1));
         r->next->val=a[i];
         r=r->next;
   }
   r->next = NULL;

   /* Список сформирован, q указывает на начало */
    
   r=pocket(q,2);  /* Запускаем сортировку */
   printf("\nresult:\n");          /*  печать результатов   */
   while (r!=NULL) {
      printf(" %d",r->val);
      r=r->next;
   }
}
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования