Countingsort und Radixsort

Code in:JavaC#PythonJavaScript

Kurz gesagt: Countingsort ordnet ganze Zahlen aus einem kleinen Bereich ohne einen einzigen Vergleich, indem er zählt, wie oft jeder Wert vorkommt: O(n + k); Radixsort wendet ihn Ziffer für Ziffer an.

Problem

Eine Million Bestellungen, hundert Zonen

Der Kurierdienst bekommt für den Tag eine Million Bestellungen. Jede hat eine Lieferzone: eine Zahl von 0 bis 99. Bevor die Transporter losfahren, werden die Bestellungen nach Zone sortiert, damit jeder Transporter seinen eigenen Stapel nehmen kann.

Mergesort macht bei einer Million Bestellungen etwa 18,7 Millionen Vergleiche, und Heapsort ist nicht besser (siehe Heapsort). Sie vergleichen Bestellung mit Bestellung, weil sie nichts über den Schlüssel wissen.

Aber hier weißt du viel: Es gibt nur hundert verschiedene Zonen. Genauso ist es bei den Bewertungen eines Produkts: von 1 bis 5. Eine Million Bestellungen zu vergleichen, um herauszufinden, dass 37 vor 38 kommt, ist Arbeit, die man gar nicht machen muss.

Die Idee

Zähle statt zu vergleichen

Der Schlüssel ist eine kleine ganze Zahl. Also kann er ein Index in ein Array sein. Das Sortieren wird zu drei Durchläufen:

1. Zählen. Ein Zähler für jede Zone. Jede Bestellung erhöht den Zähler ihrer Zone um eins.
2. Wo jede Zone beginnt. Zone 0 beginnt bei Platz 0. Zone 1 beginnt nach allen Bestellungen der Zone 0. Jeder Anfang ist der vorige plus die Anzahl der vorigen Zone. Das nennt man Präfixsumme.
3. Einsortieren. Du gehst die Bestellungen von links nach rechts durch. Jede kommt an den Anfang ihrer Zone, und der Anfang rückt um eins weiter.

Das ist Countingsort. Keine einzige Bestellung wird mit einer anderen verglichen.

Das Durchgehen von links nach rechts hat eine wichtige Folge: Die Bestellungen einer Zone bleiben in der Reihenfolge, in der sie kamen. Waren sie nach Uhrzeit sortiert, sind sie es in ihrer Zone weiterhin. Eine solche Sortierung heißt stabil. In der Lektion zur Stabilität siehst du, warum das so wichtig ist.

Sieh es dir an

Acht Bestellungen, vier Zonen

Die Zahl der Zonen ist ein Parameter. Bei der Million Bestellungen ist sie 100, hier ist sie 4, damit alles zu sehen ist:

record Order(int id, int zone) {}

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (Order o : orders) {
        out[start[o.zone()]++] = o;
    }
    return out;
}

Order[] orders = {
    new Order(101, 2),
    new Order(102, 0),
    new Order(103, 3),
    new Order(104, 2),
    new Order(105, 1),
    new Order(106, 0),
    new Order(107, 2),
    new Order(108, 3)
};
for (Order o : byZone(orders, 4)) {
    System.out.println("Zone " + o.zone() + ", Bestellung " + o.id());
}

Ausgabe

Zone 0, Bestellung 102
Zone 0, Bestellung 106
Zone 1, Bestellung 105
Zone 2, Bestellung 101
Zone 2, Bestellung 104
Zone 2, Bestellung 107
Zone 3, Bestellung 103
Zone 3, Bestellung 108

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (Order o : orders) {
        out[start[o.zone()]++] = o;
    }
    return out;
}

Schritt für Schritt, in Worten

1. Acht Bestellungen, jede mit einer Lieferzone von 0 bis 3. Ein Zähler pro Zone, alle auf 0.
2. Zählen: Jede Bestellung erhöht den Zähler ihrer Zone um eins. Keine Bestellung wird mit einer anderen verglichen.
3. Wo jede Zone beginnt: Zone 0 bei Platz 0, Zone 1 nach den zwei Bestellungen der Zone 0, bei Platz 2; Zone 2 bei 3, Zone 3 bei 6. Jeder Anfang ist der vorige Anfang plus die Anzahl der vorigen Zone.
4. Einsortieren von links nach rechts: 101 kommt an den Anfang der Zone 2, Platz 3, und der Anfang der Zone 2 rückt um eins weiter.
5. Nach Zone sortiert in 2n + k Schritten. In Zone 2 stehen die Bestellungen 101, 104, 107: in der Reihenfolge, in der sie kamen. Das ist eine stabile Sortierung.

Die Bestellungen 101, 104 und 107 liegen in Zone 2. Sie kamen in dieser Reihenfolge und gingen in dieser Reihenfolge hinaus.

start[...]++ sortiert am aktuellen Anfang ein und rückt ihn dann um eins weiter: ++ nach dem Ausdruck liefert den alten Wert.

Probier es aus

Ergänze

Der Anfang der Zone z ist der Anfang der vorigen Zone plus:

start[z] = start[z - 1] + ;

Prüfen

Die Idee

Was es kostet: O(n + k)

Jede Bestellung wird einmal gezählt und einmal einsortiert: 2n Schritte. Die Anfänge sind einer pro Zone: k Schritte. Insgesamt O(n + k), wobei k die Zahl der möglichen Schlüssel ist. Speicher: das Array der Zähler (k) und das Array mit dem Ergebnis (n).

Hier gibt es keine Vergleiche, also zählt Bench jeden Schritt des Countingsort: jedes Zählen, jeden Zähler und jedes Einsortieren. Mergesort zählt seine Vergleiche:

• Counting Sort (Zonen 0–99) O(n)
• Sortieren (Merge Sort) O(n log n)

Algorithmus	n = 10	n = 1.000	n = 100.000	n = 1.000.000
Counting Sort (Zonen 0–99)	120	2.100	200.100	2.000.100
Sortieren (Merge Sort)	21	8.709	1.536.371	18.674.993

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

Bei einer Million Bestellungen macht Countingsort 2.000.100 Schritte und Mergesort 18.674.993 Vergleiche. Die gerade Linie des Countingsort ist O(n): doppelt so viele Bestellungen, doppelt so viel Arbeit.

Genauer, für Neugierige

Kann eine Sortierung durch Vergleichen schneller sein als n log n? Nein. Bei n Elementen gibt es n! mögliche Reihenfolgen, und jeder Vergleich hat zwei Antworten. Um n! Fälle zu unterscheiden, braucht man mindestens log₂(n!) Vergleiche, und das sind etwa n log₂ n. Countingsort umgeht diese Grenze, weil er nicht vergleicht: Er benutzt den Schlüssel als Adresse.

Sieh es dir an

Radixsort: Ziffer für Ziffer

Und wenn der Schlüssel größer ist? Bulgarische Postleitzahlen haben vier Ziffern, von 1000 bis 9999: 9000 Zähler jeden Tag. Bestellnummern haben sechs Ziffern: 900.000 Zähler.

Radixsort sortiert Ziffer für Ziffer mit demselben Zählen, aber mit nur 10 Zählern. Zuerst nach der letzten Ziffer, dann nach der davor und so weiter bis zur ersten (LSD, von der niedrigstwertigen Ziffer). Jeder Durchlauf ist ein Countingsort nach einer Ziffer:

static int[] byDigit(int[] codes, int exp) {
    int[] count = new int[10];
    for (int c : codes) {
        count[c / exp % 10]++;
    }
    int[] start = new int[10];
    for (int d = 1; d < 10; d++) {
        start[d] = start[d - 1] + count[d - 1];
    }
    int[] out = new int[codes.length];
    for (int c : codes) {
        out[start[c / exp % 10]++] = c;
    }
    return out;
}

int[] codes = {4003, 1504, 9000, 1000, 8001, 4000, 1404};
for (int exp = 1; exp <= 1000; exp *= 10) {
    codes = byDigit(codes, exp);
    System.out.println(Arrays.toString(codes));
}

Ausgabe

[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1404, 1504]
[1000, 1404, 1504, 4000, 4003, 8001, 9000]

Nach dem ersten Durchlauf sind die Zahlen nach der letzten Ziffer sortiert. Nach dem zweiten nach den letzten zwei. Nach dem vierten nach allen vier.

Das funktioniert nur, weil jeder Durchlauf stabil ist. Der Durchlauf nach den Hundertern bringt die Zahlen mit gleichen Hundertern nicht durcheinander, und sie sind schon nach den letzten zwei Ziffern sortiert. 1000 und 1404 und 1504 haben dieselbe erste Ziffer: Der letzte Durchlauf lässt sie in der Reihenfolge, die sie von den früheren bekommen haben.

c / exp % 10 ist die Ziffer: 4003 / 1000 ist bei der Division ganzer Zahlen 4, und % 10 nimmt die letzte Ziffer.

Kosten: d Durchläufe mit n + 10 Schritten, wobei d die Zahl der Ziffern ist. Bei sechsstelligen Zahlen sind das 6 · (2n + 10):

• Radix Sort (6 Ziffern) O(n)
• Counting Sort (Zonen 0–99) O(n)
• Sortieren (Merge Sort) O(n log n)

Algorithmus	n = 10	n = 1.000	n = 100.000	n = 1.000.000
Radix Sort (6 Ziffern)	180	12.060	1.200.060	12.000.060
Counting Sort (Zonen 0–99)	120	2.100	200.100	2.000.100
Sortieren (Merge Sort)	21	8.709	1.536.371	18.674.993

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

Probier es aus

Sage die Ausgabe voraus

Ein Durchlauf nach der letzten Ziffer (exp ist 1). Was gibt das Programm aus?

int[] codes = {31, 12, 22, 11};
System.out.println(Arrays.toString(byDigit(codes, 1)));

Antwort

[11, 12, 22, 31]

[11, 31, 12, 22]

[31, 11, 12, 22]

Prüfen

Probier es aus

Finde den Fehler

Jemand sortiert die Bestellungen von hinten nach vorn ein. Die Zonen kommen sortiert heraus, aber innerhalb der Zone 2 stimmt etwas nicht:

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (int i = orders.length - 1; i >= 0; i--) {
        out[start[orders[i].zone()]++] = orders[i];
    }
    return out;
}

Order[] orders = {
    new Order(101, 2),
    new Order(102, 0),
    new Order(103, 3),
    new Order(104, 2),
    new Order(105, 1),
    new Order(106, 0),
    new Order(107, 2),
    new Order(108, 3)
};
for (Order o : byZone(orders, 4)) {
    System.out.println("Zone " + o.zone() + ", Bestellung " + o.id());
}

Ausgabe

Zone 0, Bestellung 106
Zone 0, Bestellung 102
Zone 1, Bestellung 105
Zone 2, Bestellung 107
Zone 2, Bestellung 104
Zone 2, Bestellung 101
Zone 3, Bestellung 108
Zone 3, Bestellung 103

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1static Order[] byZone(Order[] orders, int zones) {2 int[] count = new int[zones];3 for (Order o : orders) {4 count[o.zone()]++;5 }6 int[] start = new int[zones];7 for (int z = 1; z < zones; z++) {8 start[z] = start[z - 1] + count[z - 1];9 }10 Order[] out = new Order[orders.length];11 for (int i = orders.length - 1; i >= 0; i--) {12 out[start[orders[i].zone()]++] = orders[i];13 }14 return out;15}

Prüfen

Die Idee

Wann es nicht funktioniert

• k ist riesig. Ein Preis in Euro-Cent bis 100.000 €: 10 Millionen Zähler, um tausend Bestellungen zu sortieren. Mergesort ist nach etwa 10.000 Vergleichen fertig. Countingsort lohnt sich, wenn k etwa n oder kleiner ist.
• Der Schlüssel ist keine ganze Zahl. Namen, Adressen, Preise mit Nachkommastellen: Sie sind keine Indizes in ein Array. Radixsort kann Strings Zeichen für Zeichen sortieren, aber nur, wenn alle gleich lang oder aufgefüllt sind.
• Negative Schlüssel. Sie funktionieren, wenn du den kleinsten abziehst: Schlüssel − min beginnt bei 0.

Deshalb ist das eingebaute sort keiner der vier Sprachen ein Countingsort. Es muss alles sortieren, und das Einzige, was es über die Elemente weiß, ist, wie man sie vergleicht.

Genauer, für Neugierige

Wie es in den anderen Sprachen ist: In Java ist Arrays.sort für ein int-Array Dual-Pivot-Quicksort, in C# ist Array.Sort Introsort, in Python sort und in JavaScript sort sind Varianten des Mergesort (TimSort). Alle vergleichen. Countingsort und Radixsort schreibt man von Hand, wenn man weiß, dass der Schlüssel klein ist: Zonen, Bewertungen, Jahre, Codes. Wie die eingebauten sortieren, steht in der Lektion zur Stabilität.

Übung

Rezensionen nach Bewertung

Löse die Aufgabe in deinem Editor.

Bewertungen von 1 bis 5. Zwölf Rezensionen eines Produkts haben die Bewertungen 5, 3, 4, 5, 1, 2, 5, 4, 4, 3, 5, 2. Zähle mit einem Array von Zählern, wie viele es von jeder Bewertung gibt, gib die Zahlen aus und danach die sortierten Bewertungen, ohne einen einzigen Vergleich zweier Bewertungen.

Ausgabe

1: 1
2: 2
3: 2
4: 3
5: 4
Sortiert: [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5]

Weitere Aufgaben

• Die Rezensionen, nicht nur die Bewertungen. Jede Rezension hat einen Autor und eine Bewertung. Sortiere die Rezensionen mit byZone nach Bewertung und prüfe, dass Rezensionen mit gleicher Bewertung in der Reihenfolge bleiben, in der sie geschrieben wurden.
• Sechsstellige Zahlen. Sortiere die Bestellnummern 482113, 105990, 482100, 300001, 105911 mit Radixsort. Wie viele Durchläufe brauchst du?
• Negative Temperaturen. Sortiere die Temperaturen -3, 5, 0, -8, 12, 5 mit Countingsort. Was ziehst du von jedem Schlüssel ab?

Test

Teste dich

1. Wie viele Schritte macht Countingsort bei n Bestellungen mit Zonen von 0 bis k - 1?

Etwa 2n + k: Zählen, die Anfänge der Zonen, EinsortierenEtwa n · kEtwa n log n

2. Wann ist Countingsort eine schlechte Wahl?

Der Schlüssel ist eine Bewertung von 1 bis 5Der Schlüssel ist eine Zone von 0 bis 99Der Schlüssel ist ein Preis in Euro-Cent bis 10.000.000, und es gibt 1000 Bestellungen

3. Radixsort sortiert die Postleitzahlen zuerst nach der letzten Ziffer, dann nach der davor … Was muss jeder Durchlauf bewahren?

Nichts, jeder Durchlauf beginnt neuNur die erste ZifferDie Reihenfolge der Zahlen mit derselben Ziffer: So geht nicht verloren, was die früheren Durchläufe sortiert haben

4. Warum ist Countingsort nicht die eingebaute Sortierung der Sprachen?

Weil er langsam istWeil er nur mit kleinen ganzzahligen Schlüsseln funktioniert, während die eingebaute Sortierung alles durch Vergleichen sortiertWeil er nicht stabil ist

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Zeitkomplexität: Schritte zählen · Big-O: wie die Arbeit wächst · Mergesort und „Teile und herrsche“ · Heap und Heapsort
• Geht weiter in: Stabiles Sortieren und die eingebaute Sortierung
• Aufgaben zum Thema: Sortieren