Filter: Sortierung

Radixsort ist eine Sortierungsmethode, die Schrittweise anhand von Schlüsselwertteilen, über einen oder mehrere Sortieralgorithmen, das Eingangsfeld ordnet. Jeder Sortierungsschritt muss stabil sein, d.h. die Elementereihenfolge muss im sortierten Fall gleich bleiben. Am häufigsten wird hier Countingsort verwendet. Die Laufzeit hängt von der Anzahl der Sortierungsschritte und den gewählten Algorithmen ab.

Beispiel (Quellcode): radixsort.cpp
Download (Quellcode): radixsort.zip

Transformation

• Ganzzahlen

  Durch die Aufteilung des Schlüsselwertes, hat der darunterliegende Sortieralgorithmus keine Information, ob es sich um positive oder negative Zahlen handelt. Dies kann leicht durch hinzufügen eines Basiswertes geändert werden. Der Basiswert kann auch der kleinste Schlüsselwert sein und kann dann von allen Schlüsselwerten abgezogen werden.

• Fließkommazahlen

  Da Fließkommazahlen einen Exponenten und ein Vorzeichenbit haben, muss hier mit Vorsicht gearbeitet werden. Die Zahl selbst kann als entsprechend große…

Countingsort (Sortierung durch Zählung) ist eine Sortierungsmethode, die ohne Vergleiche funktioniert. Sie kann je nach zu sortierendem Typen und sehr viel schneller sein als Mergesort sein. Es ist aber in der normalem Implementation nötig ein Eingangs-, ein Ausgangsfeld sowie ein Hilfsfeld zu erstellen. Der Algorithmus ist besonders effektiv bei kleinen Wertebereichen der Eingangswerte, im Verhältnis zur Eingangsfeldgröße. Er funktioniert normalerweise nur mit Ganzzahlwerten, kann aber auch für andere Typen mit einer entsprechenden Transformation der Daten benutzt werden. Dieses wird näher beim Radixsort erläutert.

Beispiel (Quellcode): countingsort.cpp
Download (Quellcode): countingsort.zip

Häufigkeitsaufnahme

Zu Beginn wird ein Zählfeld erstellt, welches die Größe des erwarteten Wertebereiches besitzt. Die Zähler werden mit Null initialisiert. Nun wird der entsprechende Zähler, mit dem Index des Eingangswertes, im Zählfeld erhöht. Kurz gesagt, die Häufigkeitsverteilung wird aufgenommen.

Da dieses Zähl…

Die binäre Suche hilft sehr schnell zu entscheiden, ob ein Element in einem sortierten Datenfeld vorhanden ist. Dabei werden maximal nur log2(n) Vergleiche benötigt, die Position zu finden, an der dieses Element sein sollte sofern vorhanden.

Beispiel (Quellcode): binarysearch.cpp
Download (Quellcode): binarysearch.zip

Beschreibung

Die binäre Suche schaut in der Mitte des Datenfeldes, ob der gesuchte Wert größer oder kleiner des Feldschlüsselwertes ist. Ist er kleiner, wird der untere Teil des Datenfeldes weiter benutzt, im anderen Fall der obere. Bei nächsten Durchlauf, wird mit dem entsprechenden Teilfeld weitergearbeitet. Die Suche ist beendet, wenn nur noch ein Element vorhanden ist und dieses dem gesuchten Wert entspricht.

Aufgrund dieser Vorgehensweise, ist es unbedingt notwendig, dass dieses Datenfeld sortiert ist. Nur in diesem Fall kann davon ausgegangen werden, dass nach dem Wertevergleich, das entsprechende Teilfeld den Suchwert nicht enthalten kann.

Beispieldarstellung

In diesem Bild wird di…

Mergesort gehört auf Grund der vorhersagbaren, stabilen Laufzeit, der möglichen stabilen Sortierung und der möglichen Parallelisierung zu den beliebten Sortierverfahren. Die Anzahl der nötigen Schiebeoperationen liegt bei n*log2(n), die Anzahl der maximal benötigten Vergleiche kann durch die Summe der log(n) Durchläufe von den Zweiterpotenzen des Durchlaufs minus Eins errechnet werden.

Beispiel (Quellcode): mergesort.cpp
Download (Quellcode): mergesort.zip

Aufteilung des Feldes

Bei der rekursiven Variante ist es möglich, das Eingangsfeld immer zu halbieren (linke und rechte Hälfte), bis nur zwei oder weniger Elemente zu Verfügung stehen. Die maximale Rekursionsebene liegt bei log2 der Elementgesamtanzahl. Bei Beispielhaften 65536 Elementen also nur 16 Ebenen.

Bei der nicht rekursiven/iterativen Variante, wird direkt mit der kleinstmöglichen Teilfeldgröße (zwei Elemente) begonnen und die Teilfeldgröße in jedem Durchgang erhöht/verdoppelt. Ebenso wie bei der rekursiven Variante beträgt die Anzahl der Durc…