Algorithmus, Mergesort mit Hilfsfunktion "Partition". Klausurbeispiel mit Lösung. Wie funktioniert "Partition"?

... komplette Frage anzeigen

1 Antwort

Partition ist eigentlich das Herzstück vom Quicksort-algorithmus. Hier gibt es ein Beispiel, wie das funktioniert: https://de.wikipedia.org/wiki/Quicksort

Der Standard-mergesort-algorithmus teilt die Daten in zwei gleich große Teile. Bei Partition/Quicksort hingegen werden die Daten geteilt in kleiner oder größer das Pivot-element. Was aber, wenn das Piviot-element zufälligerweise gerade das kleinste oder das größte Element ist? Dann sind die beiden Teile eben nicht gleichgroß, sondern ein Teil enthält fast alles, der andere Teil fast nichts. In dem Fall ist dann Quicksort sehr langsam (wenn die Daten z.B. schon sortiert sind, bzw. absteigend sortiert, je nach Implementierungsvariante). Der Vorteil von Quicksort liegt eher in der sehr effizienten Implementierbarkeit, und wenn die Daten meistens unsortiert sind.

Das hier also bei Merge-sort die Partition-routine aufgerufen wird, die eigentlich von Quicksort stammt und eben nicht zwei gleich große Teile erzeugt, ist streng genommen Unsinn. Schade das soetwas gelehrt wird. Es ist für die Laufzeit sehr wichtig, ob die beiden Teile immer gleich groß sind (Mergesort), oder eben nicht (Quicksort).

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?