Plaselsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

(*) Analog zur Variante 2 von Selectsort kann hier eine Alternative zur Zählung der kleineren Elemente entwickelt werden, die dann parallelisierbar wäre.

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

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, in-place, instabil, parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit (p) Ω(nlogn) Θ(nlogn) Ο(nlogn)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 0.75*n²
Vertauschungen 0 n n

plaselsort(field A, int l, int r) {
  for i:=l to r+1 do {
    B[i]:= 0;
  }
  i:= l;
  do {
    q:= i;                        // (*)
    for j:=i+1 to r do {          // (*)
      if (A[j] < A[i]) then {     // (*)
        q++;                      // (*)
      }                           // (*)
    }                             // (*)
    p:= q + B[q];
    exchange(A[i], A[p]);
    B[q]++;
    if (p > q) B[p]++;
    while (B[i] > 0) do { i++; }
  } while (i < r);
}


Plaselsort, Variante 1