Schreiben bucket-sort in c++

Einem Buch, das ich habe, sagt dieser:

a) Stelle die einzelnen Werte der ein-dimensionalen array in einer Zeile des bucket-Arrays basierend auf dem Wert der eigenen Stelle. Zum Beispiel, 97 eingefügt, in Zeile 7, 3 gesetzt, in Zeile 3, und 100 platziert ist, die in der Zeile 0. Dies nennt man eine "Verteilung pass".

b) mit einer Schleife durch das bucket-array Zeile für Zeile, und kopieren Sie die Werte wieder auf das Originale array. Dies wird als ein "sammeln pass". Die neue Ordnung, die von den vorherigen Werten in dem eindimensionalen array ist 100, 3 und 97.

c) Wiederholen Sie diesen Vorgang für jede weitere Stelle.

Bin ich mit viel Mühe versucht zu verstehen und diese umzusetzen. Bisher habe ich:

void b_sort(int sarray[], int array_size) {
    const int max = array_size;
    for(int i = 0; i < max; ++i)
        int array[i] = sarray[i];

    int bucket[10][max - 1];
}

Ich denke, dass, um Sie zu Sortieren, indem Sie diejenigen, die Dutzende, Hunderte, etc, kann ich dieses verwenden:

for(int i = 0; i < max; ++i)
    insert = (array[i] / x) % 10;
    bucket[insert];

wobei x = 1, 10, 100, 1000, etc. Ich bin völlig verloren, wie Schreibe dies jetzt.

int get_digit(int number, int digit) { return number/int((std::pow(10.0,digit))%10;}
Das sollte funktionieren, vorausgesetzt, x == 1, 10, 100, ....
Sie möchten möglicherweise verwenden Sie hex-Ziffern, die keine dezimale Ziffern: die Verschiebung von 4*n bits und-Verknüpfung mit 0xf scheint viel natürlicher als die Verwendung einer modulo-Berechnung.
Rieck und ein Aufruf von pow...

InformationsquelleAutor Jonathan Dewein | 2012-02-16

Schreibe einen Kommentar