GobiasKoffi GobiasKoffi - 1 month ago 21
C++ Question

Radix Sort implemented in C++

UPDATE: I managed to re-work my code from scratch, and here is what I came up with. It works, but the only problem is speed. Is there any way that I can speed up my current set up using better memory management? If so, what would be the best approach?

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

void printSorted(int x[], int length);

vector < vector <int> > buckets;

void radixSort(int x[],int length){
int temp;
int m=0;
//Begin Radix Sort
for(int i=0;i<7;i++){
//Determine which bucket each element should enter
for(int j=0;j<length;j++){
temp=(int)((x[j])/pow(10,i))%10;
buckets[temp].push_back((x[j]));
}
//Transfer results of buckets back into main array
for(int k=0;k<10;k++){
for(int l=0;l<buckets[k].size();l++){
x[m]=buckets[k][l];
m++;
}
//Clear previous bucket
buckets[k].clear();
}
m=0;
}
buckets.clear();
printSorted(x,length);
}
void printSorted(int x[], int length){
for(int i=0;i<length;i++)
cout<<x[i]<<endl;
}

int main(){
int testcases;
cin>>testcases;
int input[testcases];
buckets.resize(10);
int number;
for(int i=0;i<testcases;i++){
cin>>number;
input[i]=number;
}
radixSort(input,testcases);
return 0;
}

Answer

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.