# [ACCEPTED]-Radix Sort implemented in C++-radix-sort

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

In 6 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 5 course `buckets[i+1] - buckets[i]`

will cause a buffer overflow when 4 `i`

is 9, but I omitted the extra check or 3 readability's sake; I trust you know how 2 to handle that.

With that, you just have 1 to call `radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0)`

and your array should be sorted.

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

To further 5 speed up the process, use base 256 instead 4 of base 10 for the radix sort. This only 3 takes 1 scan pass to create the matrix and 2 4 radix sort passes to do the sort. Example 1 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);
}
```

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

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

Init the second array to all 8 zeros.

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

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

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.