Diskussion:Countingsort

Automatische Archivierung

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)