[C++] Radix sort – integers sorting

I have recently written article about counting sort, a linear complexity stable sorting algorithm: C++ counting sort implementation. Now I want to introduce you another fast sorting algorithm – radix sort. It is divided into two parts: one part that divides data to sort into small chunks and second part for real sorting. Radix sort is not an ideal algorithm for sorting integers (why you should use it when you have already counting sort?), but I think it is good example that shows an idea of positioning sorting.
Let’s see the implementation:

#include  // printf, puts
#include  // srand, rand
#include  // time, clock, time_t
#include  // memset
// every programmer should know memset ;)
#define MAX 6000000 // array size
#define RANGE 1000000 // range

void radix_sort(int *, int);

// implementations of this functions you can find in
// article describing counting sort
void generate(int*, int);
void write(int*, int);
void quick_sort(int *, int, int);
void counting_sort(int *, int, int);

int main(int argc, char** argv) {
        int* T = new int[MAX];
        time_t start, end;
        long dif;

        puts("quicksort, O(nlog(n))");
        puts("counting sort, O(n)");
        // here similar code to below:

        puts("radix sort, O(n*k):");
        generate(T, MAX);
        start = clock();
        radix_sort(T, MAX);
        end = clock();
        dif = end - start;
        printf("%ld\n", dif / 1000);

        delete[] T;
        return 0;

// implementation very similar to counting sort -
// isn't it? ;)
// could be whatever function you like,
// but in this case we'll try counting sort.
// this example assumes, that processor
// uses little endian format
// int byte - which byte is it
void radix(int byte, int size, int *A, int *TEMP) {
        int* COUNT = new (int[256]);
        memset(COUNT, 0, 256 * sizeof(int));
        // multiplying by 8 to get the right bit shift
        // in next calculations.
        // 8 - the count of bits in byte.
        byte = byte << 3;
        // right shift
        // to achieve right byte.
        //  [3rd   ] [2nd    ] [1st   ] [0 byte ]
        // [++++++++ +++++++++ ++++++++ +++++++++]
        // most significant is 0-byte.
        // just counting sort:
        for (int i = 0; i < size; ++i)
                ++COUNT[((A[i]) >> (byte)) & 0xFF];
        for (int i = 1; i < 256; ++i)
                COUNT[i] += COUNT[i - 1];
        for (int i = size - 1; i >= 0; --i) {
                TEMP[COUNT[(A[i] >> (byte)) & 0xFF] - 1] = A[i];
                --COUNT[(A[i] >> (byte)) & 0xFF];
        delete[] COUNT;

// in this case in radix sort we are sorting
// parts of an integer by bytes positions.
// assuming that values of A are greater
// than 0
void radix_sort(int *A, int size) {
        int* TEMP = new (int[size]);
        // in my processor sizeof(int) is 4
        for (unsigned int i = 0; i < sizeof(int); i += 2) {
                // even byte
                radix(i, size, A, TEMP);
                // odd byte
                // reuse of TEMP array
                radix(i + 1, size, TEMP, A);
        delete[] TEMP;

Which prints:

quicksort, O(nlog(n))
counting sort, O(n)
radix sort, O(n*k):

As you see, if the range of values in array is very big radix sort can be even faster that counting sort! Moreover, execution time of radix sort is constant as long as you change range of values (not size of array!). It’s a very nice feature showing that the choice of algorithm is very important. Positioning sorting is much better in sorting strings, but it’s the topic for another article.
See also fast algorithms that sorts lists: C++ bucket sort implementation – list sorting.

This entry was posted in algorithms, c++, coding and tagged , , , , , . Bookmark the permalink.

2 Responses to [C++] Radix sort – integers sorting

  1. Philip Jones says:

    I’ve been developing my own sorting algorithm which is both faster than quicksort and counting sort. Then I realized your radix sort implementation is very fast especially when sorting 100 million 32 bit integers. I’m planning on combining the good of my own custom algorithm with the good of the radix sort implementation from this site which will make it a superior algorithm for any situation.

    I plan on developing a file compression format to compete against the zip format and other leading compression formats in the hope that mine will likely be the best after much research and development of algorithms. In future I may also develop an image format that will require minimal space.

    If you’re interested in testing or helping, let me know :)


    • codesmuggler says:

      Thanks for reading the article. It’s very good that you are developing your own skills.
      Back to the topic, it’s impossible to design better sorting algorithm that those having O(n) complexity (bucket sort, counting sort, radix sort), because you have to go trough the table at least one time. In real world quick sort O(nlogn) – for unstable sorting – and merge sort combined with insertion sort – for stable sorting – are commonly used.
      I see a lot of work to do in front of you, so good luck!

Leave a Reply

Your email address will not be published. Required fields are marked *



You may use these HTML tags and attributes: