|
Folien
Übungen
Programme
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 2: Sortieren
|
|
|
|
In vielen
Anwendugnen spielen Sortiervorgänge eine wichtige
Roll. Es sind daher zahlreiche Verfahren zum Sortieren von
Daten entworfen und analysiert worden. In diesem Kapitel
werden die bekanntesten Sortierverfahren erläutert und
untersucht. Je nachdem, welche Operation man zur Herstellung
der sortierten Reichenfolge einer gegebenen Folge von
Objekten zuläßt, unterscheidet man allgemeine und
spezielle Sortierverfahren. Allgemeine Sortierverfahren
können nur Ergebnisse von Vergleichsoperationen zwischen
den meist ganzzahlig vorausgesetzten Schlüsseln nutzen.
Spezielle Sortierverfahren können auch die Struktur der
Schlüssel ausnutzen und beispielsweise arithmetische
Operationen an Schlüsseln ausführen.
Für allgemeine Sortierverfahren ist O(n log n) eine untere
Zeitschranke, um eine Folge von n Schlüsseln zu sortieren. Man
kann allerdings Verfahren angeben, die diese Schranke unterschreiten,
wenn die gegebenen Folge bereits (bzgl. eines geeignet definierten)
Vorsortierungsmaßes bereits gut vorsortiert ist. In diesem
Kapitel werden auch verschiedene Vorsortierungsmaße und
Verfahren zum Sortieren von Daten auf Externspeichern diskutiert.
|
|
Bei Fragen zu dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|