# QuickSort



## Andrags (10. Jun 2011)

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 (10. Jun 2011)

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 (10. Jun 2011)

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


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


----------



## SlaterB (10. Jun 2011)

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 (10. Jun 2011)

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 (10. Jun 2011)

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 (10. Jun 2011)

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

MfG


----------



## Andrags (10. Jun 2011)

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


----------



## SlaterB (10. Jun 2011)

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


----------



## Andrags (10. Jun 2011)

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 (10. Jun 2011)

SlaterB hat gesagt.:


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



Öhm - instabil ist es: 



			
				Wikipedia hat gesagt.:
			
		

> 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 (10. Jun 2011)

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..


----------

