Radixsort, Variante 3 (positive Integer)

Hierbei handelt es sich um eine Beispiel-Variante für natürliche Zahlen.

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

Variante 3.a (iterativ)
Typ Beispiel (positiv integers)
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:= 0 to size(A[0])*8-1 do {
    countingsort(A, l, r, i);
  }
}

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

int getbit(int i, int d) {
  return ((i shr d) and $01);
}

Variante 3.a (iterativ)
Typ Beispiel (positiv integers)
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:= 0 to size(A[0])-1 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[ByteArray(A[i],d)]++;
  }
  for i:=1 to 255 do {
    C[i]:=C[i]+C[i-1];
  }
  for i:=l to r do {
    B[C[ByteArray(A[i],d)]-1+l]:= A[i];
    C[ByteArray(A[i],d)]--;
  }
  for i:=l to r do {
    A[i]:= B[i];
  }
}

Byte ByteArray(int v, int i) {
  return (v shr (i*8)) and $FF;  
  // besser: direkter Speicherzugriff!
}


Radixsort, Variante 3