Countingsort von englisch count zahlen ist ein stabiles Sortierverfahren das eine gegebene Folge von n displaystyle n Elementen mit linearem Zeitaufwand Problemkomplexitat O n k displaystyle textstyle O n k sortiert wenn deren Sortierschlussel naturliche Zahlen aus einem beschrankten Intervall mit k displaystyle k moglichen Werten sind oder sich darauf abbilden lassen Der Algorithmus arbeitet nicht vergleichsbasiert sondern zahlt die Vorkommnisse der Schlusselwerte er arbeitet dann adressbasiert Im Vergleich zum vergleichenden Sortieren mit der bestmoglichen Komplexitat O n log n displaystyle textstyle O n log n ergibt sich ein Vorteil wenn die Intervalllange k displaystyle k sehr klein gegenuber der Anzahl der zu sortierenden Elemente n displaystyle n ist Gut geeignetes Beispiel Sortieren aller Einwohner Bayerns n 12 85 Mio nach ihrem Alter in vollendeten Jahren k 0 150 Schlechtes nicht umsetzbares Beispiel Sortieren der Schuler einer Grundschule n 300 nach ihrem Nachnamen Zeichenkette mit max Lange 40 aus allen moglichen Buchstaben Umlauten und Sonderzeichen k 3540 Inhaltsverzeichnis 1 Algorithmus 1 1 Vereinfachter Algorithmus 2 Funktionsbeispiel 3 Komplexitat 3 1 Laufzeitanalyse 3 2 Speicherplatzbedarf 4 Literatur 5 WeblinksAlgorithmus BearbeitenCountingsort setzt voraus dass die zu sortierenden Schlusselwerte der Eingabe in einem beschrankten Intervall 0 k 1 displaystyle 0 ldots k 1 nbsp liegen oder sich einfach darauf abbilden lassen Der Algorithmus zahlt wie oft jeder dieser Werte in der Eingabe vorkommt Diese Anzahlen speichert er in einem zusatzlichen Array mit k displaystyle k nbsp Feldern ab Mit Hilfe dieses Arrays wird anschliessend fur jeden Schlusselwert die Zielposition in der Ausgabe berechnet Eingabe Array A 1 n displaystyle A 1 n nbsp mit A j 0 k 1 displaystyle A j in 0 ldots k 1 nbsp fur alle j 1 n displaystyle j 1 ldots n nbsp und die rechte Intervallgrenze k 1 displaystyle k 1 nbsp Ausgabe Feld B 1 n displaystyle B 1 n nbsp mit Inhalt von A displaystyle A nbsp in sortierter Reihenfolge Zusatzlicher Speicher Wahrend der Sortierung benotigt der Algorithmus ein Hilfs Array C 0 k 1 displaystyle C 0 k 1 nbsp Angabe des Algorithmus in Pseudocode countingsort A k C array 0 k 1 Initialisiere das Array C mit Nullen for m 0 m lt k m C m 0 end for Schreibe in C m wie haufig der Wert m in A vorkommt for j 1 j lt A size j C key A j 1 end for Adressrechnung for m 1 m lt k m C m C m 1 end for B array 1 A size Kopiere auf jeweilige Zieladresse in B mit Dekrementierung for j A size j gt 0 j B C key A j A j C key A j 1 return B Die Funktion key gibt den Sortierschlussel des Array Elements der Eingabe zuruck Wenn ein Array Element nur aus dem Sortierschlussel besteht und keine weitere Komponenten enthalt dann ist key x x displaystyle text key x x nbsp In der ersten for Schleife wird das Hilfs Array C displaystyle C nbsp initialisiert Die zweite for Schleife iteriert uber die Eingabe und inkrementiert fur jeden Sortierschlussel das zugeordnete Array Element C key A j displaystyle C text key A j nbsp C m displaystyle C m nbsp enthalt somit die Anzahl wie oft der Schlusselwert m displaystyle m nbsp in A displaystyle A nbsp vorkommt In der dritten for Schleife werden die Zahler in C displaystyle C nbsp akkumuliert so dass nach dem Ende der Schleife C x displaystyle C x nbsp die letzte Position fur ein Element mit Schlusselwert x displaystyle x nbsp im Ausgabe Array bezeichnet Somit enthalt C m displaystyle C m nbsp jetzt nicht mehr Anzahl der m Elemente in A sondern die Adresse des m Abschnitts fur B allerdings die Endadresse nicht die Startadresse Die letzte for Schleife durchlauft die Eingabe von rechts nach links aufgrund der Endadressen in C displaystyle C nbsp und sortiert den jeweiligen Eintrag dabei ein Ist die Schleife in Iteration j displaystyle j nbsp so hat A j displaystyle A j nbsp den Schlusselwert m j displaystyle m j nbsp key A j displaystyle text key A j nbsp Dieser muss also einsortiert werden an Adresse C m j displaystyle C m j nbsp Anschliessend wird die Zieladresse C m j displaystyle C m j nbsp dekrementiert damit das nachste Element in A displaystyle A nbsp welches den Schlussel m j displaystyle m j nbsp besitzt eine Position weiter vorne einsortiert wird Durch die sprungfreie Iteration wird die relative Reihenfolge von mehreren Elementen der Eingabe mit dem gleichen Sortierschlussel auch in der Ausgabe nicht verandert d h Countingsort sortiert stabil Vereinfachter Algorithmus Bearbeiten Wenn die Eingabe ein einfaches Zahlen Array ist dann kann Countingsort ohne eine Akkumulationsphase dargestellt werden countingsort A k C array 0 k 1 for m 0 m lt k m m 1 C m 0 end for for j 1 j lt A size j j 1 C A j C A j 1 end for i 0 B array 1 A size for m 0 m lt k m m 1 while C m gt 0 B i m C m C m 1 i i 1 return B Hierbei wird ausgenutzt dass es dann nicht notwendig ist die Inhalte von A nach B zu kopieren es genugt die m displaystyle m nbsp Abschnitte von B mit so vielen m displaystyle m nbsp Ganzzahlen zu fullen wie im jeweiligen C m displaystyle C m nbsp vermerkt ist Funktionsbeispiel BearbeitenAusfuhrung von Countingsort auf ein Eingabefeld A 1 8 displaystyle A 1 8 nbsp mit Elementen aus 0 5 displaystyle 0 ldots 5 nbsp mit Hilfsfeld C displaystyle C nbsp und sortierter Ausgabe in Feld B displaystyle B nbsp 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 50 0 0 0 0 01 2 3 4 5 6 7 8 Darstellung untereinander Ausgangsarray A displaystyle A nbsp Hilfsarray C displaystyle C nbsp dessen Lange vom Definitionsbereich des Arrays abhangt In das unterste Array werden die Elemente sortiert eingefugt Die obige Abbildung stellt die gegebene Zahlenfolge dar wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde indem lediglich das Array C displaystyle C nbsp mit 0 initialisiert wird Die zweite Schleife inkrementiert fur jede Ziffer deren Stelle im Array um eins 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 52 0 2 3 0 11 2 3 4 5 6 7 8 Die dritte Schleife summiert das Array C displaystyle C nbsp auf so dass dessen Inhalt angibt bis zu welcher Position ein Wert in dem sortierten Array auftaucht Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei dass die letzte der beiden Zahlen in der Folge uberhaupt nicht auftaucht also vorher in C displaystyle C nbsp an dieser Position ein 0 gewesen war In Array C displaystyle C nbsp stehen nun also statt der Anzahlen wie oft ein Wert im Array A enthalten ist stattdessen Endadressen bzw End Indizes Der letzte Wert 5 aus Array A muss an Index 8 in das Zielarray B der Wert 4 kam in Array A nicht vor und hat daher dieselbe Endadresse wie der Wert 3 die letzte 3 aus Array A muss an Index 7 in das Zielarray B anschliessend wird die Zieladresse C 3 um 1 heruntergezahlt so dass die nachste 3 aus Array A den Zielindex 6 erhalt und somit nach B 6 kopiert wird die letzte 2 aus Array A muss an Index 4 also B 4 weitere 2 er aus A mussen vor Index 4 1 kommt in A nicht vor daher hat es dieselbe letzte Zieladresse wie der Wert 0 die letzte 0 aus Array A hat die Zieladresse C 0 also 2 Sobald sie in das Array B einsortiert wurde also nach B 2 muss C 0 um 1 heruntergezahlt werden damit die nachste 0 die in Array A gefunden wird nach Index C 0 1 also in das Feld B 1 kopiert wird 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 52 2 4 7 7 81 2 3 4 5 6 7 8 In der letzten Schleife werden sukzessive die Werte aus A displaystyle A nbsp in das Array B displaystyle B nbsp ubertragen und zwar genau an der Stelle im Zielarray die das Hilfsarray C displaystyle C nbsp fur die entsprechende Zahl angibt Vor der Schleife ist dies immer die letzte Stelle an der die Zahl auftauchen wird Nach dem Ubertragen jeder Zahl wird zusatzlich der Wert in C Z a h l displaystyle C Zahl nbsp dekrementiert Die nachste gleiche Zahl wird deswegen eine Stelle weiter vorne im Zielarray eingefugt Nachfolgend die 8 Schritte Die ersten 7 Schritte im Detail 1 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 52 2 4 6 7 81 2 3 4 5 6 7 83 2 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 51 2 4 6 7 81 2 3 4 5 6 7 80 3 3 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 51 2 4 5 7 81 2 3 4 5 6 7 80 3 3 4 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 51 2 3 5 7 81 2 3 4 5 6 7 80 2 3 3 5 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 50 2 3 5 7 81 2 3 4 5 6 7 80 0 2 3 3 6 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 50 2 3 4 7 81 2 3 4 5 6 7 80 0 2 3 3 3 7 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 50 2 3 4 7 71 2 3 4 5 6 7 80 0 2 3 3 3 5 8 Schritt 1 2 3 4 5 6 7 82 5 3 0 2 3 0 30 1 2 3 4 50 2 2 4 7 71 2 3 4 5 6 7 80 0 2 2 3 3 3 5Komplexitat BearbeitenLaufzeitanalyse Bearbeiten Die Laufzeit der Funktion hangt von n displaystyle n nbsp Anzahl der Elemente des Eingabearrays und k displaystyle k nbsp die Grosse des Zahlenintervalls ab Die for Schleifen werden jeweils n displaystyle n nbsp mal oder k displaystyle k nbsp mal durchlaufen Die Zeitkomplexitat von Countingsort betragt somit O n k displaystyle mathcal O n k nbsp Speicherplatzbedarf Bearbeiten Zusatzlich zur Ein und Ausgabe die jeweils n displaystyle n nbsp Speicherfelder benotigen out of place wird noch ein temporares Array zur Speicherung der Haufigkeiten der Zahlenwerte angelegt Dieses benotigt k displaystyle k nbsp Elemente Speicherplatz Die Platzkomplexitat von Countingsort liegt also in O n k displaystyle mathcal O n k nbsp Literatur BearbeitenThomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Introduction to Algorithms 2 Auflage MIT Press Cambridge MA 2001 ISBN 0 262 03293 7 S 168 170 Donald E Knuth The Art of Computer Programming 2 Auflage Volume 3 Sorting and Searching Addison Wesley Reading MA 1997 ISBN 0 201 89685 0 S 78 englisch W Feurzeig Algorithm 23 Math Sort In Communications of the ACM Band 3 Nr 11 1960 S 601 H H Seward M I T Digital Computer Laboratory Report R 232 1954 S 25 28 Masterarbeit Weblinks Bearbeiten nbsp Wikibooks Countingsort Implementierungen in der Algorithmensammlung Interaktives Java Applet zur Demonstration Demonstration des Algorithmus Abgerufen von https de wikipedia org w index php title Countingsort amp oldid 208331827
