In der Informatik, Sorte aufzählend, ist ein Algorithmus, für eine Sammlung von Gegenständen gemäß Schlüsseln zu sortieren, die kleine ganze Zahlen sind; d. h. es ist ein Sortieren-Algorithmus der ganzen Zahl. Es funktioniert durch das Zählen der Zahl von Gegenständen, die jeden verschiedenen Schlüsselwert und Verwenden-Arithmetik auf jenen Zählungen haben, um die Positionen jedes Schlüsselwerts in der Produktionsfolge zu bestimmen. Seine Laufzeit ist in der Zahl von Sachen und dem maximalen Schlüsselwert geradlinig, so ist es nur für den Gebrauch direkt in Situationen passend, wo die Schlüssel nicht bedeutsam größer sind als die Zahl von Sachen. Jedoch wird es häufig als ein Unterprogramm in einem anderen Sortieren-Algorithmus, Basis-Sorte verwendet, die größere Schlüssel effizienter behandeln kann.

Weil das Zählen der Sorte Schlüsselwerte als Indizes in eine Reihe verwendet, ist es nicht eine Vergleich-Sorte, und der Ω (n loggen n) tiefer gebunden zum Vergleich das Sortieren ist dazu unanwendbar. Eimer-Sorte kann für viele derselben Aufgaben wie das Zählen der Sorte mit einer ähnlichen Zeitanalyse verwendet werden; jedoch, im Vergleich zum Zählen der Sorte, verlangt Eimer-Sorte, dass verbundene Listen, dynamische Reihe oder ein großer Betrag des vorzugeteilten Gedächtnisses die Sätze von Sachen innerhalb jedes Eimers halten, wohingegen das Zählen der Sorte stattdessen eine einzelne Zahl (die Zählung von Sachen) pro Eimer versorgt.

Eingang und Produktionsannahmen

Im allgemeinsten Fall besteht der Eingang zum Zählen der Sorte aus einer Sammlung von Sachen, von denen jede einen Schlüssel der natürlichen Zahl hat, dessen maximaler Wert höchstens ist.

In einigen Beschreibungen des Zählens der Sorte, wie man annimmt, ist der zu sortierende Eingang einfacher eine Folge von ganzen Zahlen selbst, aber diese Vereinfachung passt viele Anwendungen des Zählens der Sorte nicht an. Zum Beispiel, wenn verwendet, als ein Unterprogramm in der Basis-Sorte, sind die Schlüssel für jeden Anruf zum Zählen der Sorte individuelle Ziffern von größeren Artikel-Schlüsseln; es würde nicht genügen, um nur eine sortierte Liste der Schlüsselziffern zurückzugeben, die von den Sachen getrennt sind.

In Anwendungen solcher als in der Basis-Sorte ein gebundener wird der maximale Schlüsselwert im Voraus bekannt sein und kann angenommen werden, ein Teil des Eingangs zum Algorithmus zu sein. Jedoch, wenn der Wert dessen dann nicht bereits bekannt ist, kann er durch eine zusätzliche Schleife über die Daten geschätzt werden, um den maximalen Schlüsselwert zu bestimmen, der wirklich innerhalb der Daten vorkommt.

Die Produktion ist eine Reihe der Sachen in der Ordnung durch ihre Schlüssel. Wegen der Anwendung auf das Basis-Sortieren ist es wichtig, um Sorte aufzuzählen, um eine stabile Sorte zu sein: Wenn zwei Sachen denselben Schlüssel wie einander haben, sollten sie dieselbe Verhältnisposition in der Produktion haben, wie sie im Eingang getan haben.

Der Algorithmus

In der Zusammenfassung, den Algorithmus-Schleifen über die Sachen, einen histogram der Zahl von Zeiten schätzend, kommt jeder Schlüssel innerhalb der Eingangssammlung vor. Es führt dann eine Präfix-Summe-Berechnung (eine zweite Schleife, über die Reihe von möglichen Schlüsseln) durch, um, für jeden Schlüssel, die Startposition in der Produktionsreihe der Sachen zu bestimmen, die diesen Schlüssel haben. Schließlich schlingt es sich über die Sachen wieder, jeden Artikel in seine sortierte Position in der Produktionsreihe bewegend.

Im Pseudocode kann das wie folgt ausgedrückt werden:

teilen Sie eine Reihe Graf [0 zu.. k]; initialisieren Sie jede Reihe-Zelle zur Null; DANN

für jeden Eingangsartikel x:

Graf [Schlüssel (x)] = Graf [Schlüssel (x)] + 1

ganz = 0

weil ich = 0, 1... k:

c = Graf [ich]

Graf [ich] = ganzer

ganz = ganz + c

teilen Sie eine Produktionsreihe-Produktion [0 zu.. n-1]; DANN

für jeden Eingangsartikel x:

versorgen Sie x in der Produktion [Graf [Schlüssel (x)]]

Graf [Schlüssel (x)] = Graf [Schlüssel (x)] + 1

geben Sie Produktion zurück

</Quelle>

Nach dem ersten für die Schleife, versorgt die Zahl von Sachen mit dem Schlüssel, der dem gleich ist. Nach dem zweiten für die Schleife versorgt es stattdessen die Zahl von Sachen mit dem Schlüssel weniger als, der dasselbe als der erste Index ist, an dem ein Artikel mit dem Schlüssel in der Produktionsreihe versorgt werden sollte. Überall in der dritten Schleife, versorgt immer die folgende Position in der Produktionsreihe, in die ein Artikel mit dem Schlüssel versorgt werden sollte, so wird jeder Artikel in seine richtige Position in der Produktionsreihe bewegt. Die Verhältnisordnung von Sachen mit gleichen Schlüsseln wird hier bewahrt, d. h. das ist eine stabile Sorte.

Analyse

Weil der Algorithmus nur einfach für Schleifen, ohne recursion oder Unterprogramm-Anrufe verwendet, ist es aufrichtig, um zu analysieren. Die Initialisierung der Graf-Reihe und das zweite für die Schleife, die eine Präfix-Summe auf der Reihe der Zählung durchführt, wiederholt jeder in den meisten Malen und braucht deshalb Zeit. Die anderen zwei für Schleifen und die Initialisierung der Produktionsreihe, jeder braucht Zeit. Deshalb ist die Zeit für den ganzen Algorithmus die Summe der Zeiten für diese Schritte.

Weil es Reihe der Länge verwendet, und der Gesamtraumgebrauch des Algorithmus ist auch. Für Problem-Beispiele, in denen der maximale Schlüsselwert bedeutsam kleiner ist als die Zahl von Sachen, Sorte aufzählend, kann hoch raumeffizient sein, als die einzige Lagerung verwendet es anders, als seine Eingangs- und Produktionsreihe die Graf-Reihe ist, die Raum verwendet.

Verschiedene Algorithmen

Wenn jeder zu sortierende Artikel selbst eine ganze Zahl, und verwendet als Schlüssel ebenso ist, dann können die zweiten und dritten Schleifen des Zählens der Sorte verbunden werden; in der zweiten Schleife, anstatt die Position zu schätzen, wohin Sachen mit dem Schlüssel in die Produktion einfach gelegt werden sollten, hängen Kopien der Zahl zur Produktion an.

Dieser Algorithmus kann auch verwendet werden, um Doppelschlüssel, durch das Ersetzen der Reihe durch wenig Vektoren zu beseitigen, der für einen Schlüssel versorgt, der im Eingang und für einen Schlüssel da ist, der nicht da ist. Wenn zusätzlich die Sachen die Schlüssel der ganzen Zahl selbst sind, sowohl können die zweiten und dritten Schleifen völlig weggelassen werden, und der Bit-Vektor wird selbst als Produktion dienen, die Werte als Ausgleiche nicht - Einträge vertretend, die zum niedrigsten Wert der Reihe hinzugefügt sind. So werden die Schlüssel sortiert, und die Duplikate werden in dieser Variante gerade beseitigt, indem sie in die Bit-Reihe gelegt wird. Das ist wie das Sieb von Arbeiten von Eratosthenes im Wesentlichen.

Für Daten, in denen die maximale Schlüsselgröße bedeutsam kleiner ist als die Zahl von Datensachen, Sorte aufzählend, kann parallelized durch das Aufspalten des Eingangs in die Subreihe ungefähr der gleichen Größe, die Verarbeitung jeder Subreihe in der Parallele sein, um eine getrennte Reihe der Zählung für jede Subreihe, und dann das Mischen der Reihe der Zählung zu erzeugen. Wenn verwendet, als ein Teil eines parallelen Basis-Sorte-Algorithmus sollte die Schlüsselgröße (Basis der Basis-Darstellung) gewählt werden, um die Größe der Spalt-Subreihe zu vergleichen. Die Einfachheit des Zählen-Sorte-Algorithmus und sein Gebrauch leicht-parallelizable Präfix-Summe primitiv machen es auch verwendbar in mehr feinkörnigen parallelen Algorithmen.

Wie beschrieben, ist das Aufzählen der Sorte nicht ein Algorithmus im Platz; sogar die Reihe der Zählung ignorierend, muss es Eingang und Produktionsreihe trennen. Es ist möglich, den Algorithmus zu modifizieren, so dass es die Sachen in die sortierte Ordnung innerhalb derselben Reihe legt, die ihm als der Eingang mit nur die Reihe der Zählung als Hilfslagerung gegeben wurde; jedoch ist die modifizierte Version im Platz des Zählens der Sorte nicht stabil.

Geschichte

Obwohl Basis, die sich sortiert, viel länger, zurückgeht

das Zählen der Sorte und seiner Anwendung auf das Basis-Sortieren, wurde beide von Harold H. Seward 1954 erfunden.

Links

• Das Aufzählen der Sorte html5 Vergegenwärtigung
• Demonstration applet von der Universität von Cardiff
• Effiziente zählende Sorte in Haskell

.

• Eine einfache zählende Sorte-Durchführung.