Цифровая сортировка (Radix Sort) (реализация на C++)

C++   25 Март 2012  Автор статьи:  

В данной статье мы реализуем цифровую сортировку на С++. В среднем цифровая сортировка работает лучше чем быстрая сортировка. Конечно Radix Sort реализуют в разных вариантах, но в данном примере я покажу реализацию основанную на побайтовом делении числа. Если вы захотите изменить данный алгоритм на другой вид, то вам достаточно будет изменить функцию digit, которая возвращает число равное следующему сортируемому разряду. Т.е для десятичной сортировки можно было реализовать функцию digit как (n/(10^p)%10). Теперь в зависимости от длин чисел вам нужно будет выбрать K и понятно тогда, что массив c[i] содержал бы 10 элементов.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <algorithm>
#define NMAX 10
using namespace std;
int a[NMAX],b[NMAX];

int digit(int n, int p)//получение p-го байта
{
    return (n>>(8 * p) & 255);
}
int main()
{
//заполняем массив случайными числами
    for(int i = 0;i < NMAX;i++)
    {
        a[i] = rand();
    }
//максимальной число байтов в числе
    int k = sizeof(int);
//количество элементов в массиве
    int n = NMAX;
//цикл по всем байтам
    for(int i = 0; i < k; i++)
    {
//понятно что у байта максимум
//256 значений
        int c[256] = {0};
//подсчитываю количество элементов
//в массиве соответствующий каждому
//байту как и в сортировке подсчетом
        for(int j = 0; j < n; j++)
        {
            c[digit(a[j],i)]++;
        }
//модифицируем массив с
//c[i] - номер элемента
// следующего после i-го блока
        for(int j = 1; j < 256;j++)
        {
            c[j]+=c[j-1];
        }
//сдвигаем массив
        for(int j = n-1; j >-1;j--)
        {
            b[--c[digit(a[j],i)]] = a[j];
        }
        for(int j = 0; j < n; j++)
        {
            a[j] = b[j];
        }
    }
    for(int i = 0; i < NMAX; i++)
    {
        cout << a[i]<<endl;
    }
    return 0;
}

  • Алексей

    можешь объяснить, что значит : return (n>>(8 * p) & 255);

    • http://cybern.ru/ lordrp

      Общий смысл — это получение p-го байта в числе. Например, у тебя есть тип данных int, который состоит из 4 байтов. Каждый байт это число от 0 до 255. Теперь есть задача получать эти байты из числа. На физическом уровне целочисленный тип данных int представлен в виде 32 бит, поэтому я говорю, что необходимо сместиться вправо на 8 * p бит, т.е на p байт, после этого нужно просто откинуть лишние биты, чтобы осталось только 1байт, а это и делаем за счет побитового сложения с числом 255.

  • Алексей

    Спасибо

Научиться программировать

  • на Delphi

  • на Java

  • на C++