Randomized Quick Sort

Question

Ich habe den folgenden Code für randomisierten Quicksort geschrieben. Dadurch wird ein zufälliges indiziertes Element als Pivot_item in der Partitionsfunktion ausgewählt. Immer wenn ich den Code ausführe, wird p nur als 0 oder 1 gesetzt und nicht alle Indizes von 0 bis n-1 mögen es sein. Sie können dies überprüfen, indem Sie entfernen COMMENT 1 Warum passiert das und wie kann ich das beheben?

Auch das Array wird nur nach dem Index 1 richtig sortiert, wie Sie in der Ausgabe sehen können. Warum ist das und wie kann ich das beheben?

Mein letztes Problem ist, dass egal wie oft ich das Programm ausführen, bekomme ich die gleichen Elemente im Array zu Beginn mit. Soll nicht rand() jedes Mal neue Zufallszahlen generieren? Also, warum bekomme ich jedes Mal das selbe Array sortiert? Wie kann ich das beheben?

Mein Code:

Ausgang:

59 
55 
0 
2 
6 
2 
7 
7 
2 
9 
9 
9 
8 
1 
11 
12 
18 
16 
29 
23 
19 
16 
13 
22 
27 
27 
30 
31 
29 
33 
37 
21 
38 
42 
35 
42 
43 
44 
44 
46 
46 
46 
50 
50 
43 
52 
55 
55 
53 
57 

Answer 1

Zuerst, initialize the srand in der Hauptsache, z.B. mit srand(time(NULL)), um einen anständigen Zufall zu bekommen. Wenn Sie dies nicht tun, erhalten Sie die gleiche "zufällige" Reihenfolge bei jedem Programmlauf. (Sie werden dafür #include <time.h> haben.)

Zweitens, wie in den Kommentaren darauf hingewiesen, sollten Sie die Dreh mit

index = low + (rand() % (high - low)); 

wählen, ist dies, weil die Größe des Sub-Array, für die du bist Wählen Sie den Pivot ist high-low+1, die im Allgemeinen ist anders als die Größe des ursprünglichen Array (das ist, was Sie mit der sizeof Magie zu berechnen schien).

Aktualisierung. Wie Pete Becker darauf hingewiesen hat, könnte es eine gute Idee sein, srand nicht in den frühen Entwicklungsstadien zu verwenden (zum Zweck der Fehlersuche). Es ist jedoch selbstverständlich, dass es entscheidend ist, dass Sie srand verwenden, wenn Sie randomisierten Quicksort möchten.

Answer 2

Allgemeines Problem, Sie sind nicht die Größe des tatsächlichen Array immer sortiert werden:

int partition(int low,int high,int a[]) // a is just a pointer! 
{ 
    int p=sizeof(a)/sizeof(a[0]); // size of pointer/size of element 

Sie müssen um die Größe des Arrays zu übergeben. Dies ist der Grund, warum der Trick sizeof schrecklich ist. Stattdessen könnten Sie verwenden:

template <typename T, std::size_t N> 
size_t array_size(T (&)[N]) 
{ return N; } 

Dann array_size(a) Anwendung geben Ihnen einen Compiler-Fehler, da a kein Array ist. Dieses Konstrukt erscheint in vielen Bibliotheken (wahrscheinlich Boost, wird hier einen Link einfügen, sobald ich es überprüfe), und wird im Standard in C++17 sein. Es gibt auch better facilities for generating random numbers here und here for a good explanation why rand() is bad.