Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Vergleich 2)
 

 
 








Kenntnisse über die Daten sind wichtig










uvvvm.





direkt - indirekt
 
Auch wenn Quicksort in diesem Modul wohl am besten aussah:

                     Das optimale Sortierverfahren gibt es nicht.

Der Grund dafür sind die vielen möglichen Ausgangssituationen:
  • Sind die Datenmengen, die zu sortieren sind, so klein, dass sie komplett in den Arbeitsspeicher passen, so spricht man von internen Sortierverfahren.
    Andernfalls heißen die Verfahren externe Sortierverfahren. Bei externen Verfahren muss man beachten, dass Datenzugriffe möglichst günstig realisierbar sind.
  • Sind die Daten schon fast sortiert oder sind sie eher zufällig verteilt?
    Die Aufwandsanalysen im schlechtesten Fall und im Mittel sagen uns im letzteren Fall nur wenig.
  • Ist das Umspeichern von Daten zeitaufwändig oder ist der Aufwand gering?
  • Sind die Daten eindeutig oder kommen gleiche Daten mehrfach vor?
Antworten auf diese und andere Fragen sind notwendig, um jeweils ein effizientes Sortierverfahren auszuwählen.

Neben den behandeltenVerfahren gibt es noch viele andere Sortierverfahren. Einige davon entstehen aus den betrachteten durch geringfügige Modifikationen (z.B. Shakesort aus Bubblesort). Andere beruhen auf ganz anderen Ideen, die im Rahmen dieses Moduls nicht angesprochen wurden (z.B. Heapsort).

Wir formulierten alle unsere Verfahren als direkte Sortierverfahren, d.h. wir haben zur Sortierung die Datensätze explizit umgespeichert. Man kann sich statt dessen auch die vorgenommenen Umtauschungen in einem Indexvektor merken, und die Datensätze dann über den Indexvektor ansprechen. Auf diese Weise werden explizite Umspeicherungen von Datensätzen vermieden. Man spricht dann von einer indirekten Realisierung und impliziter Umspeicherung.
 
Seite 16/17