Quicksort

Es darf 3 Mal geraten werden, warum der Algorithmus so heißt!

Die Daten liegen in einer Reihung vor. Der mittlere Wert wird herausgesucht. Gibt es auf Grund einer geraden Anzahl von Werten kein mittleres Element, wird der Wert links neben der Mitte gewählt. (Es kann genauso gut der rechte Wert genommen werden. Wichtig ist nur, dass man einen nimmt!) Dieser Wert wird Pivot-Wert genannt. Nun wird die komplette Reihung so umsortiert, dass alle Werte die kleiner (oder gleich) sind als der Pivot-Wert links landen und alle größeren rechts davon. Dadurch kann sich auch der Pivot-Wert in der Reihung verschieben! Das bedeutet, dass die ursprünglich herausgesuchte Mitte nun keine Mitte mehr ist. Hier sollte klar werden, warum es nicht wirklich wichtig ist, wie genau man die Mitte bei der Suche des Pivot-Wertes trifft.

Nun hat man die Reihung in zwei Teile geteilt:

  1. Werte kleiner gleich Pivot-Wert
  2. Werte größer Pivot-Wert

Eigentlich sind es drei Teile, denn der Pivot-Wert selbst zählt weder zum ersten noch zum zweiten Teil. Der Pivot-Wert befindet sich nun schon an der richtigen Stelle in der Reihung und sollte beim weiteren Verfahren nicht mehr weiter angerührt werden.

Das Verfahren ist nun fast vollständig erläutert. Die beiden Teile werden nun genauso behandelt, wie die gesamte Reihung zuvor. Die neu entstandenen Teile auch wieder usw. . Quicksort ist also ein rekursives Verfahren.

Cookies helfen bei der Bereitstellung von Inhalten. Durch die Nutzung dieser Seiten erklären Sie sich damit einverstanden, dass Cookies auf Ihrem Rechner gespeichert werden. Weitere Information
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International