Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
12.3 Quick-Select
Hallo,
bekomme das Ausrufezeichen leider nicht eliminiert 
- Ist es bei einem bspw. 6-stelligen Bereich für die Pivotbestimmung egal ob man 1,3,6 oder 1,4,6 benutzt?
Sonst funktioniert eigentlich alles 1A.
Grüße
Ich hab das gleiche Problem… Die vorgegebenen Faelle laufen alle super, dennoch hab ich ein Ausrufezeichen im EST. Haben wir evtl das O(n) nicht eingehalten und deswegen trotz richtiger Ausgabe den Fehler?
Darüber habe ich auch schon nachgedacht. Da wir aber die optimierte Pivot-Bestimmung gegeben haben und in der Aufgabenstellung die Anleitung mit
konkret gegeben ist und ich es natürlich genau so umgesetzt habe, sollte das mit O(n) schon hinhauen. Vielleicht liegt auch ein allgemeiner Fehler vor, der das Ausrufezeichen zur Folge hat. Hat jemand schon einen grünen Haken?
Ein Tutor hat mir gerade gesagt, dass ich in meiner QuickSelectHelp den Fall nth > arraylaenge nicht gecheckt hab. Schau mal ob du dann nen Hacken kriegst.
Nein, das habe ich schon bedacht. Daran liegt es also leider nicht 
edit bzw wie soll man das handhaben?! Bei einem Array der Länge 20: Soll der Aufruf quickSelect(E[] array, int 22)/quickSelect(E[] array, int -2) auf quickSelect(E[] array, int 19)/quickSelect(E[] array, int 0) abgebildet werden?
Hat jemand vlt zufälligerweise die Ausgabe auf der Konsole?
also bei mir kommt das raus:
Chosen pivot index in ex: 0 → value: 2
Chosen pivot index in last 3 numbers of ex: 2 → value: 1
Using choosePivot and partition on array [227, 148, 683, 247, 18, 43, 290, 310, 581, 595, 94, 687, 689, 370, 381, 886, 124, 630, 622, 617]
Chosen pivot index: 9 → value: 595
Partitioned Array (pivot element in brackets):
227, 148, 247, 18, 43, 290, 310, 581, 94, 370, 381, 124, (595), 683, 687, 886, 689, 630, 622, 617
Finding the largest element: 886
Finding the second-smallest element: 43
Was wird für eine Ausgabe erwartet, wenn man das 30-größte Element haben will, dass Array aber nur 20 Elemente hat? Irgendwas, Hauptsache keine Exception oder das Maximum oder soll das Programm vorher terminieren?
dito, bis auf pivot index 0, da ich zwischen 0, 10 und 19 (und nicht 0, 9 und 19) wähle. Daran liegt es aber nicht. Hast du einen grünen Haken?
@ MannyMarc… Genau die Frage hab ich ja oben schon gestellt. Das würde mich auch interessieren.
edit: lag wohl doch an der choosePivot :nuts: … nun gehts. Danke für die Hilfe.
ja ich habe einen grünen haken
Irgendwie habe ich eine andere Ausgabereihefolge bei den Elementen, die größer als das Pivot Element sind:
Ich glaube dass kommt bei mir durch das „tauschen“ der Elemente, die größer sind als das Pivotelement.
Z.B.
wenn ich die 247 mit dem Pivot vergleiche:
Bis dahin schaut mein Array ja so aus:
227, 148, 683
Nun bekomme ich die 247 die kleiner ist als das Pivot.
Nun tausche ich also das Element 683 mit der 247
d.h. ich bekomme 227,148,247,683
oder habe ich hier irgendwo einen Denkfehler?
Hier ist der Partitionsalgorithmus in Pseudocode gegeben: https://en.wikipedia.org/wiki/Quicksort#Algorithm. Ich habe den Algorithmus so übernommen und es klappt.