Radix Sort implemented in C++

Question

I am trying to improve my C++ by creating a program that will take a large amount of numbers between 1 and 10^6. The buckets that will store the numbers in each pass is an array of nodes (where node is a struct I created containing a value and a next node attribute).

After sorting the numbers into buckets according to the least significant value, I have the end of one bucket point to the beginning of another bucket (so that I can quickly get the numbers being stored without disrupting the order). My code has no errors (either compile or runtime), but I've hit a wall regarding how I am going to solve the remaining 6 iterations (since I know the range of numbers).

The problem that I'm having is that initially the numbers were supplied to the radixSort function in the form of a int array. After the first iteration of the sorting, the numbers are now stored in the array of structs. Is there any way that I could rework my code so that I have just one for loop for the 7 iterations, or will I need one for loop that will run once, and another loop below it that will run 6 times before returning the completely sorted list?

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
    int value;
    node *next; 
};

//The 10 buckets to store the intermediary results of every sort
node *bucket[10];
//This serves as the array of pointers to the front of every linked list
node *ptr[10];
//This serves as the array of pointer to the end of every linked list
node *end[10];
node *linkedpointer;
node *item;
node *temp;

void append(int value, int n)
{
    node *temp; 
    item=new node;
    item->value=value;
    item->next=NULL;
    end[n]=item;
    if(bucket[n]->next==NULL)
    {
        cout << "Bucket " << n << " is empty" <<endl;
        bucket[n]->next=item;
        ptr[n]=item;
    }
    else
    {
        cout << "Bucket " << n << " is not empty" <<endl;
        temp=bucket[n];
        while(temp->next!=NULL){
            temp=temp->next;
        }
        temp->next=item;
    }
}

bool isBucketEmpty(int n){
    if(bucket[n]->next!=NULL)
        return false;
    else
        return true;
}
//print the contents of all buckets in order
void printBucket(){
    temp=bucket[0]->next;
    int i=0;
    while(i<10){
        if(temp==NULL){
            i++;
            temp=bucket[i]->next;                       
        }
        else break;

    }
    linkedpointer=temp;
    while(temp!=NULL){
        cout << temp->value <<endl;
        temp=temp->next;
    }
}

void radixSort(int *list, int length){
    int i,j,k,l;
    int x;
    for(i=0;i<10;i++){
        bucket[i]=new node;
        ptr[i]=new node;
        ptr[i]->next=NULL;
        end[i]=new node;
    }
    linkedpointer=new node;

    //Perform radix sort
    for(i=0;i<1;i++){
        for(j=0;j<length;j++){          
            x=(int)(*(list+j)/pow(10,i))%10;            
            append(*(list+j),x);
            printBucket(x); 
        }//End of insertion loop
        k=0,l=1;

        //Linking loop: Link end of one linked list to the front of another
        for(j=0;j<9;j++){
            if(isBucketEmpty(k))
                k++;
            if(isBucketEmpty(l) && l!=9)
                l++;
            if(!isBucketEmpty(k) && !isBucketEmpty(l)){
                end[k]->next=ptr[l];
                k++;
                if(l!=9) l++;   
            }

        }//End of linking for loop

        cout << "Print results" <<endl;
        printBucket();

        for(j=0;j<10;j++)
            bucket[i]->next=NULL;                       
        cout << "End of iteration" <<endl;
    }//End of radix sort loop
}

int main(){
    int testcases,i,input;
    cin >> testcases;
    int list[testcases];
    int *ptr=&list[0];
    for(i=0;i<testcases;i++){
        cin>>list[i];
    }

    radixSort(ptr,testcases);
    return 0;
}

Solution 1

I think you're severely overcomplicating your solution. You can implement radix using the single array received in the input, with the buckets in each step represented by an array of indices that mark the starting index of each bucket in the input array.

In fact, you could even do it recursively:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

Of course buckets[i+1] - buckets[i] will cause a buffer overflow when i is 9, but I omitted the extra check or readability's sake; I trust you know how to handle that.

With that, you just have to call radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) and your array should be sorted.

Solution 2

To speed up the process with better memory management, create a matrix for the counts that get converted into indices by making a single pass over the array. Allocate a second temp array the same size as the original array, and radix sort between the two arrays until the array is sorted. If an odd number of radix sort passes is performed, then the temp array will need to be copied back to the original array at the end.

To further speed up the process, use base 256 instead of base 10 for the radix sort. This only takes 1 scan pass to create the matrix and 4 radix sort passes to do the sort. Example code:

typedef unsigned int uint32_t;

uint32_t * RadixSort(uint32_t * a, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
uint32_t * b = new uint32_t [COUNT];    // allocate temp array
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    delete[] b;
    return(a);
}

Solution 3

Since your values are ints in the range of 0 ... 1,000,000

You can create a int array of of size 1,000,001, and do the whole thing in two passes

Init the second array to all zeros.

Make a pass through your input array, and use the value as a subscript to increment the value in the second array.

Once you do that then the second pass is easy. walk through the second array, and each element tells you how many times that number appeared in the original array. Use that information to repopulate your input array.

Comments

[Paul Biggar]

So suppose your input array size is 10. You're going to use 32MB (assuming 32-bit ints) to sort it? FYI, what you've described is radix sort with a 64 bit radix. One of the challenges in radix sort is to choose an appropriate radix that doesnt use too much space. 8bit isnt uncommon, but even a 16bit radix would take 2^16*sizeof(int) = 256KB for the auxiliary storage.

[Pit Wegner]

I'm not sure, but the way I understand it, you will in each recursion step sort only one of the buckets in the previous step. As you start with the least significant one, that means you'll have them sorted from least significant to most significant, due to the restriction to the bucket in the recursive call. Am I wrong there?

[suszterpatt]

I don't fully understand what your question is: the algorithm above is depth-first, in that the second bucket created in the first recursive call (sorting by the least significant digit) will only begin to be sorted once the first bucket has been sorted completely (up to the most significant digit). And yes, radix sort works when you go from the most significant digit to the least significant.

[Denys S.]

I believe that's called counting sort.