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.
13.2d Fehler in aufgabenstellung
Auf dem Blatt wird nach dem nth-größten Wert gesucht, in der QuickSelect Klasse wird im Kommentar nach dem nth-kleinsten Wert verlangt…
Ich nehme mal an, es zaehlt, was auf dem Blatt steht.
1 Like
Verdammt 
Nein, es geht ums nth-kleinste, also einfach um das Element, das im sortierten Array an Position nth steht.
1 Like
Hi Leute,
ich bin gerade etwas verwirrt, bei der d) habe ich es richtig verstanden, dass man das kleinste Element ausgeben soll? Oder das an der Stelle nth?
Weil in der c) heissts ja man soll links vom pivot die kleineren und rechts die größeren Werte eintragen, aber von sortiert steht da nix oder hab ich da einfach was überlesen(mehrfach)?
Soll in d) dann sortiert und dann ausgeben werden?
Sorry wenn die Frage iwie dämlich is aber ich steh grad sowas von dermaßen auf der Leitung^^
Danke schonmal^^
Es geht in der Aufgabe um QuickSelect, nicht QuickSort.
Ziel ist es, ein Element an einer bestimmten Position zu finden (das nth-kleinste, also das an der Stelle n). Dabie nutzt man aus, dass bei QuickSort das Pivot-Element seine Position nicht mehr verändert, sobald es einmal an der richtigen Stelle steht. (Da dann alle kleineren Werte links und alle größeren Werte rechts stehen.)
Es geht also bei der Aufgabe nicht darum die komplette Liste zu sortieren, sondern nur das Pivot-Element an seine richtige Stelle zu bringen, dann zu überprüfen, ob es sich an der Position befindet, für die man sich interessiert, und falls nicht entsprechend weiterzusuchen.
Du kannst dir auch mal die Übungsfolien dazu anschauen, da ist’s mit Beispiel erklärt.
Danke! Verstanden war ja nicht so schwer nur wohl schon zu spät^^
ich bin etwas verwirrt, in der main Methode steht, “Finding the second-smallest element: …” dann wird aber quickSelect mit (… , 1) aufgerufen, was ja eigentlich an erster Stelle, also das kleinste Element bedeuten würde?
oder soll man nach dem Element suchten was an der arrey[nth] Stelle steht?
Wie ict oben schon gesagt hat: Du sollst einfach das Element suchen, das den Index nth hätte, wenn der Array komplett sortiert wäre.
jemand ne Ahnung, was hieran falsch ist?:
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), 617, 683, 886, 687, 630, 622, 689
Finding the largest element: 886
Finding the second-smallest element: 43
Die Ausgabe ist richtig. Probiere aber in der main-Methode statt der Zeilen
Integer[] ex2 = java.util.Arrays.copyOf(ex, ex.length);
System.out.format("Finding the largest element: %d%n", quickSelect(ex2, ex2.length-1));
Integer[] ex3 = java.util.Arrays.copyOf(ex, ex.length);
System.out.format("Finding the second-smallest element: %d%n", quickSelect(ex3, 1));
den Code
for(int i = 0; i < ex.length; i++){
System.out.format("Finding the largest element: %d%n", quickSelect(ex, i));
}
Bei mir war mal nämlich das Problem, dass die Ausgabe für die Grenzfälle stimmt, aber in manchen Fällen eine ArrayIndexOutOfBounds-Exception vorkommt.
danke, hab das Problem mit deiner Variante gefunden 
Sollte hier nicht die 617 am Schluss stehen?
@Peterse: Ich habe dieselbe Ausgabe wie doughnut (zumindest steht am Schluss die 689) und einen grünen Haken und doughnut hat’s vermutlich mittlerweile auch gelöst.