понедельник, 26 сентября 2011 г.

Поразрядная сортировка (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.

Комментариев нет:

Отправить комментарий