Radix Sortieralgorithmus Schwierigkeiten

Question

Ich habe ein Problem zu verstehen, wie ein Benutzereingabewert als Parameter für einen Radix-Sortieralgorithmus übergeben wird.

Meine Aufgabe Klassendiagramm wird hier gezeigt. Wie Sie sehen können, muss der Klassenkonstruktor RadixSort (int radix) und (int exponent) annehmen. Die Variable "radix" dient als die numerische Basis (d. H. Basis 10) und der "Exponent" wird verwendet, um alle eingegebenen Zahlen zu sortieren.

Mein Code funktioniert perfekt, abgesehen von einem Problem: Es funktioniert nur, wenn ich das Radix direkt eingeben. Hier sind die wichtige Teile meines 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; 
} 

Von dem, was ich sagen kann, das ist, wo die Dinge schief gehen, beginnend in dem radixAlgorithm Abschnitt:

int count[10] = { 0 };

ich sollte in der Lage sein zu nehmen das Radix von Benutzereingabe. Allerdings, wenn ich versuchen, das zu tun, es in diese machen:

int count[radix] = { 0 };

ich diesen Fehler:

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

expression did not evaluate to a constant.

Da radix soll Benutzer eingegeben werden, und daher keine Konstante ist, ich nicht verstehe, wie ich sogar radix als Basis des count [] Arrays verwenden könnte.

Gibt es einen besseren Weg, dies zu tun? Habe ich es zu kompliziert gemacht? Ich verstehe einfach nicht, wie ich soll angesichts der Radixsort in irgendeiner anderen Art und Weise auszuführen, dass ich das Formular

RadixSort(int radix, int exponent);

für den Konstruktor zu verwenden gezwungen.

Irgendwelche Ratschläge oder verbesserte Methoden?

Answer 1

Sie sind bereits

mit

int * output = new int[size]; 

einen Array mit einer Größe nur zur Laufzeit bekannt zu vergeben. Wenn Sie das verstehen, können Sie den gleichen Ansatz verwenden, um einen int * count zuzuweisen, der genauso funktioniert. Sie müssen es selbst auf 0 initialisieren, und delete [] das resultierende Array, wenn Sie fertig sind.

---

Sie könnten stattdessen ein std::vector verwenden, wie Patrick Robert im Kommentar vorgeschlagen, dies ist der geeignetere Weg, um es in C++ zu tun, und es hat den Vorteil, sich von Aufheben der Zuordnung, wenn es aus dem Geltungsbereich:

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

---

int count[radix] ist ein variabler Länge Array, die in neueren Versionen von C vorhanden ist, aber nicht C++ (siehe Why aren't variable-length arrays part of the C++ standard?).