Radixsort, Variante 2 (Strings)

Hierbei handelt es sich um eine Beispiel-Variante für Strings.

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

Variante 2.a (iterativ)
Typ Beispiel (strings, lexikografische Ordnung)
Eigenschaften iterativ, out-of-place, stabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(dn) Θ(dn) Ο(dn)
Interpretationen 2d*n 2d*n 2d*n
Kopierungen 2d*n 2d*n 2d*n

radixsort(field A, int l, int r) {
  for i:= maxlength(A)-1 downto 0 do {
    countingsort(A, l, r, i);
  }
}

countingsort(field A, int l, int r, int d) {
  for i:= 0 to 255 do {
    C[i]:= 0;
  }
  for i:= l to r do {
    C[getid(A[i],d)]++;
  }
  for i:=1 to 255 do {
    C[i]:=C[i]+C[i-1];
  }
  for i:=l to r do {
    B[C[getid(A[i],d)]-1+l]:= A[i];
    C[getid(A[i],d)]--;
  }
  for i:=l to r do {
    A[i]:= B[i];
  }
}

int getid(String S, int i) {
  if (S.length > i) then {
    return CharToInt(S[i]);
  } else {
    return 0;
  }
}

int maxlength(field A) {
  l:= 0;
  for i:= l to r do {
    if (A[i].length > l) then {
      l:= A[i].length;
    }
  }
  return l;
}


Radixsort, Variante 2