Countingsort, Variante 3 (ohne Duplikate)

Hierbei handelt es sich um eine alternative verbesserte Variante. Die Idee ist einfach: Eine eineindeutige Abbildung erspart Zeit und Speicherplatz.

Eine rekursive Realisierung (Variante 3.b) ist möglich.

Variante 3.a (iterativ)
Typ alternativ, optimiert
Eigenschaften iterativ, in-place, stabil, (parallelisierbar)
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n+k) Θ(n+k) Ο(n+k)
Interpretationen n n n
Generierung n n n

countingsort(field A, int l, int r, int k) {
  for i:= 0 to k-1 do parallel {
    C[i]:= 0;
  }
  for i:= l to r do {
    C[A[i]]++;
  }
  c:=0;
  for i:=0 to k-1 do {
    for j:=1 to C[i] do {
      A[l+c]:= i;
      c++;
    }
  }
}


Countingsort, Variante 3