randomisierte Schnellsortierung [stürzt bei einigen Eingaben ab]

Question

Ich habe die Codes entfernt, weil es Hausaufgaben sind. Wenn Sie die Hilfe wirklich brauchen, können Sie entweder auf die Diskussion mit George B (unten) oder auf PM schauen.

---

Hallo Leute. Dies ist eine Hausaufgabe. Ich habe es mit anderen Sortieralgorithmen getestet, und Q.S. ist der einzige, der bei einigen zufälligen Eingaben abstürzt.

Das Programm wird verlassen lang (mit anderen Sachen), aber Eingang wird zufällig generiert ....

verbrachte ich ein paar Stunden die Codes Verfolgung und konnte immer noch keinen Fehler herauszufinden .... QS ist wahrscheinlich sehr einfach für die Fachleute, also hoffe ich, Hinweise auf dieser Durchführung zu erhalten.

Irgendein Eingang wird geschätzt!

---

Frage: Was ist "zufällig"?

A: Ein Teil der Generation ist enthalten.

void randomArray(unsigned long*& A, unsigned long size) 
{ 
//Note that RAND_MAX is a little small for some compilers (2^16-1). 
//In order to test our algorithms on large arrays without huge 
//numbers of duplicates, we'll set the high-order and low-order 
//parts of the return value with two random values. 
A = new unsigned long[size]; 
for(unsigned long i=0; i<size; i++) 
    A[i] = (rand()<<16) | (rand()); 

//Another note: initially, if you want to test your program out with smaller 
//arrays and small numbers, just reduce A[i] mod k for some small value k as in the following: 
//A[i] = rand() % 16; 
//this may help you debug at first. 
} 

Q: Welche Art von Fehler?

Nun, ich bekomme keine Kompilierung Fehler. Ohne Q.S. kann ich andere vier Sortieralgorithmen ohne Probleme ausführen (ich kann die Sortierung kontinuierlich ausführen). Wenn Q.S aktiviert ist, nachdem das Programm ein- oder zwei- oder dreimal ausgeführt wurde, oder sogar beim ersten Ausführen, wird das Programm beendet (ich benutze Eclipse, damit die Konsolen enden).

geben die Anzahl der Elemente oder eine negative Zahl zu beendigen: 5 { Einige Arrays

}

Auswahl sort dauerte 0 Sekunden. Merge Sortierung dauerte 0 Sekunden. schnelle Sortierung dauerte 0 Sekunden. Heap Sortierung dauerte 0 Sekunden. Bucket Sortierung dauerte 0 Sekunden. { Ausgabe von 5 sortiert Arrays

}

geben die Anzahl der Elemente oder eine negative Zahl zu beendigen: 6 { Einige Arrays

}

Auswahl sort dauerte 0 Sekunden. Merge Sortierung dauerte 0 Sekunden. schnelle Sortierung dauerte 0 Sekunden. Heap Sortierung dauerte 0 Sekunden. Bucket Sortierung dauerte 0 Sekunden.

{Leistung von 5 sortiert Arrays}

die Anzahl der Elemente eingeben oder eine negative Zahl zu beendigen: 8 { } Arrays --- --- Konsole endet

Wieder das Problem ist, dass es ziemlich oft abstürzt, also deutet das darauf hin, dass es eine hohe Wahrscheinlichkeit für Zugriffsverletzungen gibt, aber wenn ich mehr als 10 Verfolgungen mache, sehe ich das Problem nicht .... (vielleicht habe ich meinen Gehirnstapel überlastet - _ -)

Danke.

Answer 1

Hinweis:

q is unsigned (the result of the partition function) 
so, q-1 is also unsigned 
what if q is zero? 

(Es ist Hausaufgaben, so dass Sie es herausfinden müssen, ich denke :))

Answer 2

Ihr Algorithmus {2,5,2} mit dem Array Trace

. Offensichtlich stürzt Ihr Programm ab, sobald doppelte Nummern in Ihrer Liste sind. Der erste Aufruf der Partition gibt 2 als Index r zurück. Somit wird der zweite Anruf von quickSort(A,3,2) auf Speicherstellen zugreifen, die nicht innerhalb der Feldgrenzen liegen. Es ist immer eine gute Idee, die Grenzkontrollen für Arrays manuell durchzuführen und verständliche Ausgaben zu generieren, um Ihr Programm leichter verfolgen und debuggen zu können.