Tepifsort, Variante 2 (temporäres Zeigerfeld)

Hierbei handelt es sich um das Grundgerüst eines temporären Zeigerfeldes. Das Prinzip wird im Folgenden an der Standardvariante von Bubblesort demonstriert.

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

Variante 2.a (iterativ)
Typ standard, Beispiel
Eigenschaften iterativ, in-place, stabil, nicht parallelisierbar
Datenstrukturen einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen n n n

tepifsort(listele first, listele last) {
  i:= -1;
  for ele:= first.prev to last.next do {
    B[i]:= ele;
    i++;
  }
  l:= 0;
  r:= i-2;
  bubblesort(B, l, r);
  for i:= l to r+1 do {
    B[i]^.prev  := B[i-1];
    B[i-1]^.next:= B[i];
  }
}

bubblesort(listele[] B, int l, int r) {
  for i:=r downto l+1 do {
    for j:=l to i-1 do {
      if (B[j]^ > B[j+1]^) then {
        exchange(B[j], B[j+1]);
      }
    }
  }
}


Tepifsort, Variante 2