Sortieralgorithmus

Bücher

Angebote / Angebote:

Quelle: Wikipedia. Seiten: 42. Kapitel: Quicksort, Bubblesort, Heapsort, Mergesort, Sortierverfahren, Stabilität, Countingsort, Topologische Sortierung, Insertionsort, Shellsort, BottomUp-Heapsort, Radixsort, Selectionsort, Swap-Sort, Timsort, Slowsort, Stoogesort, Binäre Priorisierung, Combsort, Bogosort, Binarytreesort, Shakersort, Bucketsort, Gnomesort, Adaptiertes 2-Phasen-2-Band-Mischen, Merge Insertion, Introsort, SocialRank, Hybridsort, Samplesort, Simplesort, Smoothsort, Median Cut. Auszug: Countingsort (von engl. count "zählen") ist ein einfaches, stabiles Sortierverfahren. Es sortiert eine gegebene Zahlenfolge nicht durch Vergleiche, sondern setzt das Wissen voraus, aus welchem Intervall die Zahlen des Schlüssels stammen. Die zu sortierenden Zahlen liegen in für ein festes, im Voraus bekanntes . Dann bestimme für jedes zu sortierende Element die Anzahl der Elemente, welche in der sortierten Reihenfolge vor liegen, und platziere damit an die korrekte Stelle. Feld mit für alle . Als Parameter werden übergeben. Feld mit Inhalt von in sortierter Reihenfolge. Zudem wird bei dem Sortierverfahren ein Hilfsvektor benötigt. Der nachfolgende Pseudocode bezieht sich auf die in der Problemstellung benutzten Bezeichnungen. COUNTINGSORT(A, B, k)1 for i = 0 to k2 do C = 03 for j = 1 to length4 do C] = C] + 1 //C gibt nun an, wie oft i in A vorkommt.5 for i = 1 to k6 do C = C + C //C gibt nun die Anzahl der Elemente <= i in A an, //bzw. die Stelle mit dem größten Index, an dem //das Element i im sortierten Array stehen wird.7 for j = length downto 18 do B]] = A9 C] = C] - 1 Ausführung von Countingsort auf ein Eingabefeld mit Elementen aus mit Hilfsfeld und sortierter Ausgabe in Feld . Darstellung untereinander Ausgangsliste , Hilfsvektor , dessen Länge vom Definitionsbereich der Liste abhängt. In unterster Liste werden die Elemente sortiert eingefügt. Die Obige Abbildung stellt die gegebene Zahlenfolge dar, wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde, indem lediglich der Vektor mit 0 initialisiert wird. Zweite Schleife inkrementiert für jede Ziffer deren Stelle im Vektor um eins. Die dritte Schleife summiert den Vektor auf, so dass dessen Inhalt angibt, bis zu welcher Position ein Wert in der sortierten Liste auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, dass die letzte der beiden Zahlen in der Folge überhaupt nicht auftaucht, also vorher in an dieser Position ein 0 gewesen war. Nun folgt die letzte Schleife. In dieser