Sortierprinzipien

Beim Sortieren gibt es zwei grundlegende Vor- oder Herangehensweisen, die ich so explizit noch nirgendwo beschrieben fand:

  • Entweder wird die komplette Startmenge sortiert, das allerdings, weil ein Durchgang nicht ausreicht, um das Ordnungsniveau bis zur völligen Sortiertheit anzuheben, sooft wie nötig wiederholt wird. Die Menge wird also in jedem Durchlauf genaugenommen nur teilsortiert („Gesamtmenge teilsortiert“).
  • Oder es wird nur ein Teil der Startmenge sortiert, dieser aber von Anfang an in nur einem Durchgang vollständig, und dieser Teil wird durch Hinzunahme immer weiter Elemente aus der unsortierten Menge immer mehr vergrößert, bis es keine unsortierte Elementemenge mehr gibt („Teilmenge komplettsortiert“). Das entspricht dem sog. Teile-und-herrsche-Prinzipg („divide et impera“).

Viele, wenn nicht sogar die meisten Sortieralgorithmen lassen sich mehr oder weniger eindeutig einem dieser beiden Prinzipien zuordnen. Es gibt aber auch Sortieralgorithmen, die sich beider Heransgehensweisen bedienen, so Quicksort und - was nicht offensichtlich ist - Stupidsort.

Deutlich unterscheidbar sind beide Prinzipien auch in diesem Programm in der sog. Combobox „Vorsortierung/-mischung“ rechts oben im Bedienformular. Je nach Sortierprinzip kann bzw. muß das Maß der Vorsortierung unterschiedlich eingestellt werden. Nur beim Merge- und beim Quicksort ist das nicht ganz korrekt, denn beide sind eigentlich rekursiv und wurden in eine iterative Ersatzstruktur transformiert.

Möglicherweise hängt die Klassifikation in stationäre und nichtstationäre Sortieralgorithmen damit zusammen.

Während die erste Teilmenge überwiegend von iterativen Algorithmen realisiert wird, werden für die zweite eher rekursive Algorithmen verwendet.

Kontaktformular