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

[Все сортировки]

Теория: Wikipedia

Практика: acmp.ru

Реализация:

Условимся, что мы обрабатываем только массив неотрицательных целых чисел.

Первая реализация обрабатывает разряды десятичного числа начиная с младших. Количество разрядов в числе задается в константе RADIX_AMOUNT.

1. typedef unsigned int UINT;
2. . . .
3. void radix_sort10(UINT* &a, int size) {
4.   UINT* b = new UINT[size];
5.   UINT* title = new UINT[10];
6.   UINT* count = new UINT[10];
7.   UINT* prev = new UINT[size];
8.  
9.   memset(count,0,sizeof(UINT) * 10);
10.   char curDig;
11.   int osn = 10;
12.   int del = 1;
13.   for (int r=0;r<RADIX_AMOUNT;r++) {
14.     for (int i=0;i<size;i++) {
15.       curDig = (a[i] % osn) / del;
16.       prev[i] = title[curDig];
17.       title[curDig] = i;
18.       count[curDig]++;
19.     }
20.     int bPos = size;
21.     for (int i=9;i>=0;i--) {
22.       while (count[i]) {
23.         b[--bPos] = a[title[i]];
24.         title[i] = prev[title[i]];
25.         count[i]--;
26.       }
27.     }
28.     osn *= 10; del *= 10;
29.     swap(a,b);
30.   }
31.   delete[] b;
32.   delete[] title;
33.   delete[] count;
34.   delete[] prev;
35. }

* This source code was highlighted with Source Code Highlighter.

Вторая реализация обрабатывает цифру, состоящую из 8 байт. Т.е. исходное число обрабатывается в системе счисления с основанием 256 и содержит не более 4 цифр.

1. void radix_sort256(UINT* &a, int size) {
2.   UINT* b = new UINT[size];
3.   UINT* title = new UINT[256];
4.   UINT* count = new UINT[256];
5.   UINT* prev = new UINT[size];
6.   UINT mask[4] = {0x000000FF,
7.         0x0000FF00,
8.         0x00FF0000,
9.         0xFF000000};
10.  
11.   memset(count,0,sizeof(UINT) * 256);
12.   unsigned char curDig;
13.   for (int r=0;r<1;r++) {
14.     for (int i=0;i<size;i++) {
15.       curDig = a[i] & mask[r];
16.       prev[i] = title[curDig];
17.       title[curDig] = i;
18.       count[curDig]++;
19.     }
20.     int bPos = size;
21.     for (int i=255;i>=0;i--) {
22.       while (count[i]) {
23.         b[--bPos] = a[title[i]];
24.         title[i] = prev[title[i]];
25.         count[i]--;
26.       }
27.     }
28.     swap(a,b);
29.   }
30.   delete[] b;
31.   delete[] title;
32.   delete[] count;
33.   delete[] prev;
34. }

* This source code was highlighted with Source Code Highlighter.