mergesort oder/und quicksort ?

[Jaipur]

Hi,

sind quicksort und mergesort die gleichen Algorithmen?

Ich sehe da echt keinen Unterschied, kann mich da mal jemand bitte aufklären!

[gajUli]

Noe, sind nicht das selbe. Mergesort ist irrsinnig alt (von Neumann 1945), Quicksort kam ueber 20 Jahre spaeter .

Quicksort ist im Durchschnitt am schnellsten, dafuer ist Merge-Sort worst-case-optimal.

[Orffi]

Beide Algorithmen arbeiten nach dem "teile und herrsche"-Prinzip. Das bedeutet, man teilt ein Problem in zwei kleinere Probleme

auf und hofft, daß das kleinere Problem lösbar ist. Wenn dem nicht so ist, dann verkleinert man das Problem weiter. Aus der Beschreibung sieht man schon, daß man die beiden Probleme ganz gut rekrusiv implementieren kann. (Muß man aber nicht, wenn man will kann man die Rekursion auflösen.) Es gibt auch ein paar unterschiede, die jeweils den einen oder anderen Algorithmus bevorzugen.

Mergesort sortiert Teillisten. Um das zu bewerkstelligen teilt Mergesort die Listen solange auf (halbiert sie), bis die Liste nur noch aus einem Element besteht. Jetzt kann man die Listen sortieren und fügt sie nun wieder zusammen. Am Ende hat man eine sortierte Liste.

Quicksort funktioniert ein wenig anders: Hier nimmt man sich ein Element (x) aus der Liste und sortiert alle Elemente die kleiner als x sind nach links und die Elemente, die größer sind, nach rechts. Das wird dann rekursiv für die ganze Liste gemacht. Dieses x sollte man natürlich einigermaßen schlau wählen... Am Ende bekommt man auch hier die sortierte Liste heraus.

Beide Algorithmen besitzen im average case die Komplexität n*log n. Wobei n die Anzahl der Elemente sind. Im ungünstigsten Fall (worst case) hat Quicksort allerdings die Komplexität n².

HTH

Jan

[Jaipur]

Hi,

so wie ich das jetzt verstanden habe, ist der einzigste Unterschied der Median der bei QuickSort "eingesetzt" wird.

Aber was bedeutet denn jetzt "worst case"?

[Orffi]

Nee, der Median wird nicht eingesetzt. Der einfachste Quicksort hat auch gar nichts mit Mittelwerten zu tun. Quicksort nimmt sich das Element (z.B.) aus der Mitte und fängt an, alle Elemente, die kleiner als dieses Element sind, nach links zu sortieren und die größeren Elemente nach rechts.

Worst case bedeutet im ungünstigsten Fall, daß heißt wenn die zu sortierenden Daten in einer ungünstigen Reihenfolge vorliegen. Für Quicksort würde der worst case so aussehen: Die Liste mit der Länge n wird in eine Liste der Länge n-1 und 1 aufgeteilt. Die Liste mit n-1 Elementen wird dann in n-2 Elemente und 1 aufgeteilt usw. Daraus ergibt sich dann das n². Wie die Daten dann vorliegen müssen, wenn ich das Element immer aus der Mitte der zu sortierenden Liste auswähle, um den worst case zu erreichen, kannst Du Dir ja mal spaßigerweise überlegen.

HTH

Jan