Frage von BillHatayu, 20

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

Hallo, am Montag schreibe ich die Klausur "Algorithmen und Datenstrukturen". Hocke seit gestern vor einer Probeklausur mit Lösung. Hier steht etwas über die "Hilfsfunktion Partition", es ist sogar der Code angegeben, aus dem ersichtlich sein sollte, wie die Funktion funktioniert. Ich verstehe es aber nicht.

Unten wird in der Lösung gezeigt, wie "Partition" einen 5-stelligen Array in nur zwei Zeilen richtig sortiert. Zuerst tauscht er nur die 12 mit der 5 aus, aber in der nächsten Zeile sind plötzlich 2, 3, 5 und 7 alle an der richtigen Position.

Die Musterlösung ist als Bild hochgeladen.

Hoffentlich kann mir jemand helfen, diese Funktion kommt nämlich für alle möglichen Sortieralgorithmen (Quicksort, Insertionsort, Mergesort) ran.

Es wäre toll, wenn jemand in Worten beschreiben kann, wie die Hilfsfunktion "Partition" vorgeht?

Vielen Dank

Antwort
von Maimaier, 6

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

Keine passende Antwort gefunden?

Fragen Sie die Community