Problem mit Quicksort Sortier-Algorithmus

[Devon]

Hallo, ich bin gerade dabei den Quicksort Sortier-Algorithmus zu lernen habe aber irgendwie ein Problem damit.

Als Sortierbeispiel nehme ich einfach mal folgende Zahlenfolge die in einer verketteten Liste oder in einem 1D Array steht.

591763

Pivot-Element ist das ganz rechte also die 3

Jetzt gehe ich von links aus nach rechts und suche eine Zahl die größer ist als die 3 - dort treffe ich direkt auf die 5 welche größer als die 3 ist. Dann gehe ich von rechts aus nach links und suche eine Zahl die kleiner ist als die 3 - also treffe ich auf die 1. Diese beiden Zahlen werden nun getauscht.

195763

Ich suche nun wieder von links aus eine Zahl die größer ist als die 3 und treffe auf die 9 - von rechts aus suche ich eine Zahl die kleiner als 3 ist und treffe dabei auf die "größer-als-pivot-makierung", also abbruch. Nun wird das Pivotelement mit der betroffenen Zahl getauscht und es wird links und rechts vom Pivotelement getrennt.

1|3|5769

Links vom Pivotelement sind nun alle Zahlen kleiner als das Pivotelement und rechts davon sind alle Zahlen größer als das Pivotelement.

Da die 1 und die 3 einzeln stehen sind sie nun laut Definition fertig sortiert. Also kümmer ich mich um den rechten Block. Und hier kommt nun mein Problem:

Ich nehme wieder das ganz rechte Element als Pivotelement - also die 9. Ich suche von links aus eine Zahl die größer ist. Was jetzt?

Endlossschleife

Oder soll ich einfach abbrechen wenn links von dem Pivotelement keine größere Zahl mehr steht UND wenn ich von rechts aus suchend über das Pivotelement laufe!?

Ich muss das ganze in C# programmieren und sehe schon endlose Programmiersessions vor mir

 

[hostile]

Warum machst du dir soviel Mühe?

Hier steht der Pseudo-Code: http://de.wikipedia.org/wiki/Quicksort

gruß
hostile

 

[little_skunk]

Es kommt hoffentlich keine Endlosschleife zustande. Du nimmst die 9 und suchst ab der 3 nach rechts eine Zahl, die größer ist als 9. Du wirst keine Zahl finden. Das bedeutet, dass die 9 schon sortiert ist. Nun machst du mit 5,7,6 weiter und würdest die 6 als Pivotelement nehmen. Wie es dann weiter geht weißt du ja bereits

@hostile
Ich finde es gut, dass er sich die Mühe macht und selber denkt. So versteht er den Algorithmus und kann ihn vor allem auch selber auf diverse andere Fälle anwenden. Ich habe schon genügend Programmierer gesehen, die mit Quicksort zwar Zahlen sortieren können solange die Lösung zum Abschreiben funktioniert aber schon bei Buchstaben oder ganzen Strings bekommen sie auf einmal Probleme. Abschreiben hat nichts mit Programmieren zu tun. In diesem Fall ist es zwar Pseudocode aber das läuft auf das gleiche hinaus.

 

[hostile]

Na gut, als Anfänger macht es schon Sinn, aber später im Job möchtest du das Rad selten neu erfinden

gruß
hostile

 

[McGizmo]

Na gut, als Anfänger macht es schon Sinn, aber später im Job möchtest du das Rad selten neu erfinden

gruß
hostile

Natürlich nicht aber wenn man von Anfang an alles bereits vorgekaut bekommt steht man später schön doof da wenn man doch mal einen Algorithmus selbst entwickeln muss. :P