Radix Sorting algorithm difficulties

Question

I'm having a problem understanding how to pass a user-input value as a parameter for a Radix Sorting algorithm.

My assignment class diagram is shown here. As you can see, the class constructor RadixSort is required to take (int radix) and (int exponent). The "radix" variable serves as the numerical base (i.e. base 10) and the "exponent" is used to sort all input numbers.

My code works perfectly, except for one problem: it only works when I input the radix directly. Here are the important parts of my code:

RadixSort(int radix, int exponent): SortRoutine() {
cout << "Radix: " << radix << endl;
cout << "Exponent: " << exponent << endl;
setRadix(radix);
setExponent(exponent);
}

void sort(int array[], int size) {
    cout << "-Initiating Radix Sort-" << endl;
    setSize(size);

    int max = getMax(array, size);
    int radix = getRadix();
    int * output = new int[size];

    for (int exponent = getExponent(); max / exponent > 0; exponent *= radix) {
        radixAlgorithm(array, size, radix, exponent, output);
    }
}

void radixAlgorithm(int array[], int size, int radix, int exponent, int output[]) {

    int i;
    int count[10] = { 0 };

    for (i = 0; i < size; i++)
        count[(array[i] / exponent) % radix]++;

    for (i = 1; i < radix; i++) {
        count[i] += count[i - 1];
    }

    for (i = size - 1; i >= 0; i--) {
        output[count[(array[i] / exponent) % radix] - 1] = array[i];
        count[(array[i] / exponent) % radix]--;
    }

    for (i = 0; i < size; i++)
        array[i] = output[i];

    for (i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

From what I can tell, this is where things go wrong starting in the radixAlgorithm section:

int count[10] = { 0 };

I'm supposed to be able to take the radix from user input. However, if I try to do that, making it into this:

int count[radix] = { 0 };

I get this error:

array type 'int[radix]' is not assignable.

expression did not evaluate to a constant.

Because radix is supposed to be user input, and therefore not a constant, I dont understand how I could even use radix as the base of the count[ ] array.

Is there a better way to do this? Did I make it too complicated? I just dont understand how I'm supposed to perform the Radix Sort in any other way given that I'm forced to use the form

RadixSort( int radix, int exponent);

for the constructor.

Any advice or improved methods?

Have you considered using [`std::vector`](http://en.cppreference.com/w/cpp/container/vector)? — Patrick Roberts, Jun 05 '16 at 19:59

score 0 · Answer 1 · edited May 23 '17 at 12:08

You're already using

int * output = new int[size];

to allocate an array of a size known only at runtime. If you understand that, you can use the same approach to allocate an int * count which will work the same way. You need to initialize it to 0 yourself, and delete [] the resulting array when finished.

You could instead use a std::vector as Patrick Roberts suggested in the comment, this is the more appropriate way to do it in C++, and it has the benefit of deallocating itself when it goes out of scope:

std::vector<int> count(radix, 0);

int count[radix] is a Variable Length Array, which is present in newer versions of C but not C++ (see Why aren't variable-length arrays part of the C++ standard?).

This worked very well, dont know why I couldn't see that I'd already done it before. Thanks for the help. — xChaos, Jun 07 '16 at 05:53

Radix Sorting algorithm difficulties

1 Answers1