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
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier ist ein Eimer Sortieren Sie basierend auf den Informationen, die in der OP-Frage.
Hinweise Über ein 2d-array für den Eimer verschwendet viel Platz... ein array von Warteschlangen/Listen in der Regel mehr Sinn macht.
Ich normalerweise nicht in C++ Programmieren, und der obige code geschrieben wurde, im web-browser, also syntax-Fehler vorhanden sind.
Ich nehme an, Sie können nicht
int bucket[10][max+1];
weil die Größe eines Arrays auf dem stack muss zur Kompilierzeit bekannt ist.InformationsquelleAutor Louis Ricci
Den folgenden code verwendet hex-Ziffern für eine bucket-sort (für
BITS_PER_BUCKET=4
). Natürlich ist es so gemeint ist lehrreich, nicht produktiv.InformationsquelleAutor Eugen Rieck
einer Neufassung der Louis-code in C++11 mit STL-Warteschlangen.
InformationsquelleAutor hesham safi