QuickSort

[Andrags]

Huhu,

ich habe noch ein kleines Problem:
Ich habe heute eine QuickSort implementiert, die einen Comparator übergeben bekommen kriegt, der
zum T passt, und ein passendes T[] Array.

Die Methode hat auch funktioniert, bis ich gemerkt habe das ich in der Aufgabe überlesen habe, das ich
das Pivot Element mit hilfe der 3 Meridan Methode bestimmen soll. Also habe ich eine Extramethode zur bestimmung des 3 Meridan Pivots geschrieben und die übrigen Methoden ein wenig abgeändert.

Jetzt habe ich aber das seltsame Problem, das das Array zwar korrekt geordnet wird, jedoch
die Methode scheinbar nicht abbricht (Stackoverflow) und ich finde den Fehler nicht mehr, kann mir
jemand helfen?

 

[SlaterB]

du kannst natürlich hoffen, dass jemand den Code im Kopf verarbeitet und den Fehler direkt sieht, klappt oft genug,
für alle anderen normal-sterblichen wäre aber eine main-Methode mit Beispiel-Array usw. nützlich..

 

[Andrags]

Natürlich, sorry! Ich nehme meine JUnit Tests immer für gegeben


//Ich werde die Methoden nach Bewertung wieder Online stellen.

 

[SlaterB]

ich erhalte eine Ausgabe
1
2
4
6
7
8
9
12
17
57

und danach Programmende, einen Fehler kann ich dann erstmal nicht vermuten,
wie sieht denn der StackTrace aus der bei dir kommt oder welche anderen Infos hast du?

setze in jede Schleife, jede rekursive Methode oder sonstige verdächtige Code-Stelle ein System.out.println("Stelle ..");
kommt irgendeine dieser Ausgaben zu oft?

 

[Andrags]

Der Main scheint bei mir auch zu funktionieren, also poste ich dir mal die JUnit 3 Tests, da wird der Fehler geworfen:

// Ebenso hier

Irgendwo scheint er nicht abzubrechen

 

[SlaterB]

ich persönlich kann dazu nichts direkt sagen, werde ich auch nicht ausprobieren,
wenn eine unbekannte unnötige Blackbox wie ein JUnit-Test Mist macht, dann ist mir das nur Recht,

nochmal die Tipps wie zuvor mit besonderen Augenmerk auf Beginn und Ende der Code-Teile, die du bestimmst,
wenn es außerhalb weiterläuft, dann wäre es interessant, ob das auch passiert wenn du in deinen Methoden den Code quasi streichst und am Ende nur noch

public void testQuicksort()  {
        System.out.println("testQuicksort Start");

        System.out.println("testQuicksort Ende");
}

hast, aber das wird bei dir doch nicht so sein oder? obwohl andererseits genauso unverständlich ist dass mit Code darin irgendwas schiefgeht..,

falls bei vollem Code der Fehler auftritt, bei quasi leerer Methode nicht,
dann schaue nach ob durch andere halbe Kürzungen der Fehler eine Zeit noch besteht und irgendwann weggeht,
diesen Wechsel-Punkt zu bestimmen ist dann aus Hauptaugenmerk

wenn doch auch bei leerer Methode ohne Quicksort irgendwas schief läuft, dann mache ein neues Thema auf mit Konzentration auf JUnit..

 

[Andrags]

Ich versuch mich nochmal, aber du hast mich n stückchen weitergebracht, ich sag bescheid wenn ich den fehler gefunden habe.

MfG

 

[Andrags]

Kurze Frage: Quicksort ist ja instabil, heißt das, das wenn ein Element doppelt vorkommt, das die Sortierung crasht?

 

[SlaterB]

der Definition nach nicht
Stabilität (Sortierverfahren) ? Wikipedia

 

[Andrags]

Weil mir grade aufällt das der fehler nur auftritt, wenn ein element 2x vorhanden ist, wie es der fall in stringarray ist

edit: ... was ich hier nicht gepostet habe ;D

 

[Andi_CH]

der Definition nach nicht
Stabilität (Sortierverfahren) ? Wikipedia

Öhm - instabil ist es:

Beispiele für instabile Sortierverfahren:
Bogosort, Heapsort, Introsort, Quicksort, Shellsort, Smoothsort, Slowsort, Stoogesort, Selectionsort

Aber ich denke deine Aussage bezog sich auf das Crashen - das sollte IMO kein Sortierverfahren crashen nur weil gleich Werte vorkommen

 

[thorstennn]

Die Reihenfolge gleicher Elemente in der Eingabefolge bleibt in der Ausgabefolge erhalten wäre stabil.

Was ich aber noch nicht verstehe, wird bei moveToEnd immer das letzte Element verstaucht? Dann wäre es doch selction sort..