Radix Sort implemented in C++

Question

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 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.

Answer 2

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.