Diskussion:Countingsort

Zum Archiv

Wie wird ein Archiv angelegt?

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Zu komplizierte Erklärung

Ich bemängele folgende Sachen am Artikel:

1. In den Schleifen des Pseudocodes müsste ein "<" anstatt eines "<=" stehen. Ich hab ihn in Java getestet.
2. Die Komplexität beträgt im Pseudocode Beispiel O( 2n ) anstatt O(n + k).
3. Wenn man die Werte der letzten Schleife nicht in B, sondern in A einfügt, kann man einen Speicherplatzbedarf of O( k ) anstatt von O( n+k ) haben.
4. Das Beispiel ist zu komplex. Das lässt sich viel einfacher erklären.

Kommt jemand auf die gleichen Ergebnisse wie ich oder wo ist mein Denkfehler? --Piegames (Diskussion) 13:01, 8. Jan. 2015 (CET)

Sprichst du vom "Vereinfachten Algorithmus"? --Martin Thoma 10:11, 9. Jan. 2015 (CET)

Ja, aber im ersen Pseudocode sehe ich teils ähnliche Fehler --Piegames (Diskussion) 14:29, 9. Jan. 2015 (CET)

Ok, ich habe das mal mit Python implementiert und getestet. So klappt es:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def countingsort(A, k):
    """Alle natürlichen Zahlen im Array A sind im Intervall [0, k]."""
    C = [0 for i in range(k+1)]

    # Speichere wie häufig jede Zahl vorkommt
    for element in A:
        C[element] += 1

    # Initialisiere neuen Array
    j = 0
    B = [0 for i in range(len(A))]

    # Schreibe jede Zahl so häufig wie nötig in den neuen Array
    for i in range(k+1):
        while C[i] > 0:
            B[j] = i
            C[i] -= 1
            j += 1
    return B


if __name__ == '__main__':
    import random
    mixed = [i for i in range(10)]
    random.shuffle(mixed)
    print(mixed)
    print(countingsort(mixed, 50))

    mixed = [random.randint(0, 10) for _ in range(30)]
    print(mixed)
    print(countingsort(mixed, 50))

zu 1.: Ich bin mir nicht sicher, was die Notation array(0, k) bedeuten soll. Aber ja, mit der Indizierung / < / <= ist was komisch. @Mateusz87: Hast du den Pseudocode eventuell geschrieben? Kannst du die array(i, j)-Notation erklären?

zu 2.: Die Laufzeitkomplexität dieses Codestücks ist ${\mathcal {O}}(2\cdot {\text{Länge von A}}+k)={\mathcal {O}}({\text{Länge von A}}+k)$. Das sollte also im Artikel passen. Das $k$ ist wichtig, weil $k$ um größenordnungen größer sein kann als die Länge von $A$ (z.B. wenn man einfach den Integer-Bereich wählt).

zu 3.: Nein. Du musst ja A gespeichert haben. Es könnte ja z.B. k=2 sein und len(A) = 10000000 oder auch umgekehrt k=100000 und len(A) = 2.

Viele Grüße, --Martin Thoma 16:41, 9. Jan. 2015 (CET)

Kann ich allem zustimmen, nur 3. nicht. Ich nehme als Beispiel den Python Code (mit dem Pseudocode geht es genau so):

    # Schreibe jede Zahl so häufig wie nötig in den neuen Array
    for i in range(k+1):
        while C[i] > 0:
            A[j] = i // !
            C[i] -= 1
            j += 1
    return A // !

Im Abschnitt wird auf A nicht zugegriffen, weder lesend noch schreibend. B ist leer und wurde nicht verändert. Man muss A nicht einmal zurücksetzen, da A nur geschrieben wird (Und nicht beispielsweise inkementiert wie C). Im Endeffekt spart man sich die Initialisierung eines weiteren Arrays.

Die array(i, j) Notation habe ich übrigens auch nicht so recht verstanden.

--Piegames (Diskussion) 17:59, 9. Jan. 2015 (CET)

Ich habe mich glaube ich nicht deutlich ausgedrückt: Ja, natürlich kann man A überschreiben und sich B sparen. Aber das ändert nichts an der Speicherplatzkomplexität von ${\mathcal {O}}(n+k)$ (wenn man den Eingabeparameter mit zählt). --Martin Thoma 21:46, 9. Jan. 2015 (CET)

Man kann A nur überschreiben, wenn einfach nur Ganze Zahlen sortiert werden sollen. Wenn A aber ein Datensatz ist, von dem der Schlüssel nur ein Teil darstellt, dann benötigt man B.

"man [kann] A überschreiben und sich B sparen" ist also ein Spezialfall, der i.A. nicht möglich ist.

--arilou (Diskussion) 13:59, 6. Feb. 2015 (CET)

zu 1): Nein, '<=' ist richtig, wenn die Arrays mit [1] beginnen. Das machen A und B, das Array C beginnt bei C[0].

zu 2): O( 2n ) ist Murks, konstante Faktoren werden weggelassen, also: O( n ) (bzw. O( n+k ))

zu 3): siehe mein voriger Edit - auf B verzichten geht nur in speziellen Fällen. (Wie dem "Vereinfachten Algorithmus".)

zu 4): Countingsort ist etwas schwieriger; ich habe versucht, die Erklärung etwas auszubauen. Wenn du es "einfacher erklären" kannst - gerne doch, du darfst.

--arilou (Diskussion) 14:16, 6. Feb. 2015 (CET)

Praktisches Beispiel

Ich finde die Erklärung auch sehr kompliziert. Tatsächlich ist es ja so, dass das Sortierverfahren nur für ganz spezielle Aufgaben sinnvoll und praktizierbar. Ich würde das an einem Beispiel erläutern. Möchte man 100 Schüler nach dem Alter sortieren, so wird man wohl ein Vergleichsverfahren anwenden. Wenn man die Schüler nur nach dem Jahrgang sortieren will, wird man für jeden Jahrgang einen Topf bilden und jeden Schüler in den passenden Topf stecken. Ein solches Beispiel würde ich an den Anfang stellen. --Suricata (Diskussion) 15:30, 6. Feb. 2015 (CET)

Finde ich eine gute Idee; hab' mal zwei an die Einleitung angehängt. --arilou (Diskussion) 10:30, 25. Okt. 2016 (CEST)

Link zur Demonstration mit Java

Einige moderne Browser unterstützen kein Java mehr oder Sicherheitseinstellungen unterdrücken die Verwendung von Applets.Ohne weitere Einstellungen funktioniert es auf Mac weder mit Chrome, Safari oder Firefox. Man könnte den Link in Zukunft entfernen oder einen Hinweis dazu schreiben, sonst wundert man sich, warum der Link nicht funktioniert. Da ich nicht weiß, was von beiden sich eher anbietet, hab ich es erstmal so gelassen und lediglich einen funktionierenden Link hinzugefügt. (nicht signierter Beitrag von Bcgam3r (Diskussion | Beiträge) 12:29, 14. Jan. 2017 (CET))

Countingsort - Einleitung - Beispiele

Servus, als schlecht umsetzbares Beispiel wird die Sortierung nach Nachnamen genannt. Tatsächlich ist das aber ziemlich gut umsetzbar, man darf nur nicht den Raum der möglichen Nachnamen zum zählen wählen, sondern beschränkt sich auf die Buchstaben a-z (oder ASCII, oder UTF-8...) und sortiert dann den Ebenen nach. Wenn es mehr als 2 Treffer für einen Buchstaben in einer Ebene gibt, muss man noch mal ein entsprechendes Teilfeld eine Ebene tiefer sortieren. Mit der Herangehensweise erhält man das sortierte Feld mit minimal möglichen Tauschvorgängen. Ein nicht umsetzbares Beispiel wäre das Sortieren von Gleitkommazahlen, weil man die nicht auf natürliche Zahlen abbilden und damit nicht in einem konstanten Feld zählen kann, das kleiner unendlich ist. Mit getrickse könnte man die vlt. noch in String-Repräsentation sortieren, wenn man Rundungsfehler in Kauf nähme, oder wenn die Nachkommastellen eingeschränkt wären. Das würde man wieder wie Wörter sortieren und hätte ein recht kleines Zählfeld. Ich finde das Beispiel sollte man entsprechen ändern. Vlt. gibt es noch ein einfacher verständliches Schlechtbeispiel als Gleitkommazahlen, aber das genannte Nachnamen Beispiel halte ich für falsch. VG Martin (4.11.2011)

Du 'erfindest' damit aber einen anderen Sortieralgorithmus - und zwar baust du praktisch den Radixsort nach. (Alternativ Bucketsort, rekursiv.)

Bei Radixsort steht übrigens auch, wie/dass man ähnliches wie mit deinen Strings durchaus auch mit Gleitkommazahlen machen kann...

Nochmal deutlich: "Das Gegenbeispiel xyz ist schlecht, weil man es mit dem (anderen, ähnlichen) Sortierverfahren B durchaus sortieren kann." ~ nope.

--arilou (Diskussion) 10:13, 5. Nov. 2021 (CET)