Gezählt
Verschiebungen
Zähler

  • Wird gezählt
  • Gerade verschoben
  • Platziert

Mehr über Countingsort

Countingsort

Countingsort funktioniert, wenn die Werte ganze Zahlen in einem kleinen Bereich sind. Das Verfahren hat einen Zähler für jeden möglichen Wert, zählt, wie oft jeder vorkommt, und weiß aus diesen Zählerständen genau, wohin jeder Wert gehört. Sehen Sie zu, wie sich die Zähler beim Lesen der Liste füllen und dann wieder leeren, während jeder Wert in seinen Abschnitt wandert, eine Verschiebung nach der anderen. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ eine Verschiebung nach der anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Der Streifen zwischen der Liste und der Pufferzeile enthält einen Zähler für jeden Wert. Die Kacheln zeigen die gezählten Werte, die Verschiebungen und die Zähler. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene ganze Zahlen ein. Probieren Sie eine Liste mit wenigen verschiedenen Werten.
  2. Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Wert nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
  3. Achten Sie auf die Zähler: Sie füllen sich, während die Liste gelesen wird, und zählen dann herunter, während jeder Wert platziert wird.

Wie Countingsort funktioniert

Legen Sie einen Zähler für jeden Wert vom kleinsten bis zum größten an. Lesen Sie die Liste einmal und erhöhen Sie den Zähler jedes Werts, den Sie sehen, um eins. Summieren Sie dann die Zählerstände ab dem kleinsten Wert auf: Der Abschnitt eines Werts beginnt direkt nach allen kleineren Werten. Gehen Sie zum Schluss die Liste noch einmal durch, verschieben Sie jeden Wert an den nächsten freien Platz seines Abschnitts, und kopieren Sie das Ergebnis zurück.

Schnell bei kleinem Bereich

Countingsort liest die Liste zweimal und geht die Zähler einmal durch, daher wächst der Aufwand mit n + k: der Zahl der Werte plus der Zahl der Zähler. Bei vielen Werten in einem kleinen Bereich, etwa Prüfungspunkten von 0 bis 100 oder Altersangaben, schlägt das jedes vergleichsbasierte Sortierverfahren. Bei einem großen Bereich verschwendet es Zeit und Speicher für Zähler, die niemand braucht: Drei Werte zwischen 1 und 1.000.000 bräuchten eine Million Zähler. Außerdem ist es der Schritt, den Radixsort für jede Ziffer wiederholt.

Häufig gestellte Fragen

Wie funktioniert Countingsort?

Das Verfahren zählt, wie oft jeder Wert vorkommt, summiert die Zählerstände auf, um zu finden, wo der Abschnitt jedes Werts beginnt, und verschiebt dann jeden Wert direkt an den nächsten freien Platz seines Abschnitts. Es vergleicht nie zwei Werte.

Wann lohnt sich Countingsort?

Wenn die Werte ganze Zahlen sind oder sich in solche umwandeln lassen und der Bereich vom kleinsten bis zum größten Wert nicht viel größer ist als die Zahl der Werte: Noten, Alter, kleine Codes. Dann braucht es Zeit proportional zu n + k.

Ist Countingsort stabil?

Ja, wenn die Werte wie hier in Listenreihenfolge an den nächsten freien Platz ihres Abschnitts verschoben werden. Deshalb kann Radixsort es für jede Ziffer verwenden.

Warum nicht einfach jeden Wert so oft schreiben, wie er gezählt wurde?

Für reine Zahlen funktioniert das und ist sogar einfacher. Echte Daten enthalten aber meist mehr als den Schlüssel, etwa einen Namen zu jeder Punktzahl, und beim Schreiben der gezählten Schlüssel ginge das verloren. Werden die Elemente selbst verschoben, bleibt alles beisammen.

Werden meine Zahlen irgendwohin gesendet?

Nein. Die Sortierung läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor