Startseite
Informatik
Algorithmen
DRUCK
2004
2005
2006
2007
2008
2009
Sortieren
BucketSort
RadixSort
QuickSort
MergeSort
HeapSort
BubbleSort
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
Sortieren
Wie können Elemente einer Liste in die richtige Reihenfolge gebracht werden?
Wie können Elemente einer Liste in die richtige Reihenfolge gebracht werden?
Einführung
Definitionen zum Thema Sortieren
Sortieren
Sortieren ist die Umordnung einer Folge von Objekten in eine geordnete Folge.
In der Folge können natürlich auch Objekte vorkommen, die bezüglich der Ordnungsrelation gleichrangig sind.
[INFODUDEN]
Die zu sortierenden Objekte bzw. Elemente liegen meist in einer Array-ähnlichen Struktur vor, sodass jedes Objekt direkt über einen Index (slot) mit der Laufzeitkomplexität O(1) angesprochen werden kann. Dies ist die Grundlage für schnelles Sortieren.
Die zu sortierenden Objekte bzw. Elemente liegen meist in einer Array-ähnlichen Struktur vor, sodass jedes Objekt direkt über einen Index (slot) mit der Laufzeitkomplexität O(1) angesprochen werden kann. Dies ist die Grundlage für schnelles Sortieren.
Schlüsselwert
Sortiert werden Objekte bzgl. ihrer Schlüsselwerte.
Beispielsweise können Warenhausartikel bzgl. ihres Preises sortiert werden, dann wäre der Preis eines Warenhausartikels der Schlüsselwert und der Warenhausartikel das zu sortierende Objekt. An anderer Stelle können Warenhausartikel auch bzgl. ihrer Kategorie, ob Spielzeug, Bekleidung oder Möbel, sortiert werden.
Häufig werden Zahlen bzgl. ihrer Größe sortiert, dann sind die Objekte zugleich auch die Schlüsselwerte selbst.
Beispielsweise können Warenhausartikel bzgl. ihres Preises sortiert werden, dann wäre der Preis eines Warenhausartikels der Schlüsselwert und der Warenhausartikel das zu sortierende Objekt. An anderer Stelle können Warenhausartikel auch bzgl. ihrer Kategorie, ob Spielzeug, Bekleidung oder Möbel, sortiert werden.
Häufig werden Zahlen bzgl. ihrer Größe sortiert, dann sind die Objekte zugleich auch die Schlüsselwerte selbst.
Stabilität
Sortierverfahren heißen
stabil,
wenn sie die relative Reihenfolge gleichrangiger Objekte nicht verändern.
Die Stabilität ist wichtig, wenn die Objektfolge bereits bezüglich einer anderen Ordnungsrelation vorsortiert ist.
1
Beispielsweise kann die Medaillen-Rangliste bei einer Olympiade mit einem stabilen Sortierverfahren erstellt werden:
Beispielsweise kann die Medaillen-Rangliste bei einer Olympiade mit einem stabilen Sortierverfahren erstellt werden:
- zunächst sortiert man nach Bronze
- dann nach Silber
- und schließlich nach Gold
Glattheit
„Man nennt ein Sortierverfahren
glatt
(englisch: smooth),
wenn es
n
verschiedene Schlüssel im Mittel in
O(n log n)
und
n
gleiche Schlüssel in
O(n)
Schritten zu sortieren vermag mit einem
glatten
Übergang zwischen diesen Werten”,
heißt es in
[ALGODAT].
Mit einem glatten Sortierverfahren wird zwar die Best-Case-Laufzeit O(n) eher selten erreicht, aber allein Laufzeiten, die zwischen O(n) und O(n log n) liegen, können komplexere Anwendungen in ihrer Rechenzeit schon extrem beschleunigen.
Mit einem glatten Sortierverfahren wird zwar die Best-Case-Laufzeit O(n) eher selten erreicht, aber allein Laufzeiten, die zwischen O(n) und O(n log n) liegen, können komplexere Anwendungen in ihrer Rechenzeit schon extrem beschleunigen.
Intern vs. Extern
Man unterscheidet
interne
und
externe
Sortierverfahren.
Befindet sich der gesamte Datenbestand während des Sortierens im Hauptspeicher, so spricht man von internen Sortierverfahren.
Falls der überwiegende Teil des Datenbestandes während des Sortierens überwiegend auf Hintergrundspeichern
(Speicherhierachie)
verbleibt, spricht man von externen Verfahren.
[INFODUDEN]
Das externe Sortieren wird bei sehr großen Datenbeständen (Größer als Kapazität des Hauptspeichers) angewandt.
Das Problem des externen Sortierens lässt sich auf das des internen Sortierens zurückführen. Eine zu sortierende Datei wird in mehrere Teile, die klein genug sind, aufgeteilt, um diese intern sortieren zu können. Schließlich werden diese sortierten Dateifragmente zu einer großen sortierten Datei zusammengemischt (MergeSort). [INFO94]
Wenn das zugrundliegende Betriebssystem über einen beliebig großen virtuellen Speicher verfügt, können prinzipiell auch beliebig große Dateien intern sortiert werden. Jedoch verlangsamt sich der Sortierprozess beim Sortieren einer sehr großen Datei (größer als der Arbeitsspeicher) erheblich, da die zeitaufwendigen Zugriffe auf prozessorferne Speichermedien zunehmen. Deshalb werden Sortierverfahren, die die Anzahl der Zugriffe auf prozessorferne Speichermedien minimieren, als externe Sortierverfahren bezeichnet. Der MergeSort zählt von seiner Art her zu den externen Sortierverfahren und kann leicht auf das Sortieren großer Dateien spezialisiert bzw. optimiert werden.
Das externe Sortieren wird bei sehr großen Datenbeständen (Größer als Kapazität des Hauptspeichers) angewandt.
Das Problem des externen Sortierens lässt sich auf das des internen Sortierens zurückführen. Eine zu sortierende Datei wird in mehrere Teile, die klein genug sind, aufgeteilt, um diese intern sortieren zu können. Schließlich werden diese sortierten Dateifragmente zu einer großen sortierten Datei zusammengemischt (MergeSort). [INFO94]
Wenn das zugrundliegende Betriebssystem über einen beliebig großen virtuellen Speicher verfügt, können prinzipiell auch beliebig große Dateien intern sortiert werden. Jedoch verlangsamt sich der Sortierprozess beim Sortieren einer sehr großen Datei (größer als der Arbeitsspeicher) erheblich, da die zeitaufwendigen Zugriffe auf prozessorferne Speichermedien zunehmen. Deshalb werden Sortierverfahren, die die Anzahl der Zugriffe auf prozessorferne Speichermedien minimieren, als externe Sortierverfahren bezeichnet. Der MergeSort zählt von seiner Art her zu den externen Sortierverfahren und kann leicht auf das Sortieren großer Dateien spezialisiert bzw. optimiert werden.
in-place vs. out-of-place
Man spricht von einem
In-Placement-Sortierverfahren,
wenn ein internes Sortierverfahren direkt auf der Eingabestruktur ohne Verwendung zusätzlichen Speicherplatzes sortiert.
Die Speicherplatzkomplexität bleibt mit O(n) bestehen; das n-stellige Eingabewort liegt nur einfach im Speicher vor, belastet aber nicht den Algorithmus selbst. Die Speicherauslastung des jeweiligen Algorithmus wird nur noch von seiner Art her geprägt. Beispielsweise benötigen iterative, in-place Algorithmen in der Regel einen Speicherplatz von O(1), wohingegen rekursive, in-place Algorithmen ziemlich viel Stack verbraten können; es sei denn, man verwendet ausschließlich repetetiv rekursive Algorithmen.
Das Gegenteil von in-place wird als out-of-place bezeichnet. Algorithmen, welche out-of-place arbeiten, haben in der Regel mindestens eine Speicherauslastung von O(n) wie zum Beispiel der RadixSort.
Die Speicherplatzkomplexität bleibt mit O(n) bestehen; das n-stellige Eingabewort liegt nur einfach im Speicher vor, belastet aber nicht den Algorithmus selbst. Die Speicherauslastung des jeweiligen Algorithmus wird nur noch von seiner Art her geprägt. Beispielsweise benötigen iterative, in-place Algorithmen in der Regel einen Speicherplatz von O(1), wohingegen rekursive, in-place Algorithmen ziemlich viel Stack verbraten können; es sei denn, man verwendet ausschließlich repetetiv rekursive Algorithmen.
Das Gegenteil von in-place wird als out-of-place bezeichnet. Algorithmen, welche out-of-place arbeiten, haben in der Regel mindestens eine Speicherauslastung von O(n) wie zum Beispiel der RadixSort.
Fußnote
- Die Idee des RadixSort gründet auf der Stabilität eines Sortiervorgangs, es gibt keinen nicht-stabilen RadixSort. Im Gegensatz dazu ist die Stabilität eines Sortierverfahrens meist nur abhängig von der Implementierung, nicht aber von der Idee.
Quellenangabe
-
[INFODUDEN]
-
[ALGODAT]
-
[INFO94]