- Wir sortieren sortierten kram und sortieren weiter mit sortiertem kram
- Gibt es Algos die schnell sind und vllt nicht vergleichsbasiert sind?
- Halt dinge die einfach die Struktur der Eingabe Nutzen anstelle sich durchzukämpfen
- Wir haben schlüssel, und die sind kleine natürliche Zahlen
- Wir nutzen ein Arra von anfangs leeren Behältern
- Wenn wir etwas eingeben sortieren wir das dann direkt in den Behälter mit dem passenden Index ein
- Am ende hängen wir alle behälter (buckets) direkt aneinander
- Dann haben wir den kram erstmal so definiert, und soweit sortiert, dass die richtig "geordnet" sind
- Laufzeit:
- Wir nehmen KSort als Baustein um größere Schlüssel zu sortieren.
- Annahme: Schlüssel haben bis zu d Ziffern,
- Ansatz: Wir wenden dann KSort auf alle d Ziffern an.
- Sprich, wir sortieren erst nach zahlen der 1. stelle, dann der 2. stelle etc.
- §%37%§
- Wir nehmen einfach Radix-Sort, und sortieren von hinten, also letzte stelle der zahl, dann vorletzte etc.
- Korrektheit folgt aus KSort
- §%21%§
- Wir machen das anhand der größten Ziffer, und dann sortieren wir inenrhalb der behälter mit einem genaueren, langsamen algo
- Das kann aber dazu führen, dass unser kram am ende langsam(er) wird, und das dann deswegen irgendwie problematisch wird