Arbeitsweise

Unter den oben genannten Veraussetzungen, kann der CountingSort sehr einfach aus aufeinanderfolgenden Schritten aufgebaut werden.

  1. Falls das größte Element MAX nicht bekannt ist, wird dieses herausgefunden werden.
  2. Ein Temporärarray counts von der Größe MAX + 1 wird angelegt und alle seine Felder auf 0 initializiert.
  3. In einem Durchgang durch die Originalmenge wird die Häufigkeit der Elemente gesammelt. Diese Information wird in counts abgelegt.
  4. Diese Häufigkeiten werden aufsummiert. counts[i] += counts[i-1]
  5. Aufgrund der gesammelten Häufigkeiten, kann nun die Sortierung in einer linearen Zeit geschehen. Das sortierte Feld wird zunächst in einer Hilfsmenge abgelegt.
  6. Die Hilfsmenge, welche die sortierte Ordnung der Originalmenge wiederspiegelt, wird zurück kopiert.
  7. Das Temporärarray kann nun freigegeben werden.

Der Trick, der auch die Beschränkungen erklärt, ist das Verwenden der Werte der Elemente als Indizes in der Tempoärmenge. Beim Zählen der Häufigkeiten wird ein Element mit dem Wert k benutzt, um im counts-array das k-te Elemente um eins zu inkrementieren.


\begin{picture}(15,4) % psframe(0,0)(15,4) \par\put(.2,2.2){\footnotesize {Orig... ...le(3.5,1.5){.7} \psline{->}(3.5,2.3)(3.5,3.5)(11.5,3.5)(11.5,2.3) \end{picture}

Wie in der Zeichnung ersichtlich wird, benutzt der CountingSort die Elemente selbst als Indizes in einem anderen Array. Nun ist auch erkennbar wieso das Hilfsarray, in der Lage sein muss, MAX + 1 Elemente aufzunehmen. Wird das größte Elemente aus der Originalmenge zur Indizierung des Hilfsarrays benutzt, so kommt es zu keinem Fehlzugriff, da das Array groß genug ist. Das ``+ 1'' erklärt sich dadurch, daß, erstens, die Menge die 0 enthalten kann, und, zweitens, Arrays in C orientierten Sprachen ``nullindiziert'' angesprochen werden. Beim Sammeln der Information über die Häufigkeit der Elemente wird im count-array durch das Element indizierte Feld inkrementiert.

Im count-array ist nun angegeben wie oft, ein Element mit dem Wert 0, mit dem Wert 1, ...mit dem Wert MAX in der Originalmenge vorkommt. Auf einem Array bestehend nur aus Zahlen würde es reichen, das count-array zu durchgehen und der Reihe nach die Indizes in die Originalmenge, so oft wie im count[k] angegeben, nacheinander zukopieren (siehe Abschnitt Optimierung). Handelt es sich jedoch um Elemente, die aus komplexen Sturkturen aufgebaut sind, so das diese einfachen Methode nicht ausreicht, ist ein Kopiervorgang der Originalelemente erforderlich. Dazu werden die Häufigkeiten aufaddiert. Die Summe in einem bestimmen Feld counts[k] gibt somit an, wieviele Elemente vor das k-Element gehoeren. Somit gibt der Wert die absolute Position des Elements an. Das Aufbauen des sortierten Feldes erfolgt jedoch in einem zweiten temporären Feld der Größe des Originalfeldes, um ein überschreiben der noch benötigten Elemente zu vermeiden. Schliesslich wird die temporäre Menge in das originale Feld kopiert, womit der Algorithmus terminiert.

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Laufzeitkomplexität Aufwärts: CoutingSort Vorherige Seite: Bedingungen   Inhalt

2002-05-09