Avlsort, Variante 3 (Tepif)

Hierbei handelt es sich um eine alternative Variante. Die Idee ist einfach: Ein temporäres Indexfeld (bidirektional) spart Speicherplatz, Kenntnisse über die Elemente und reduziert das Risiko eines Datenverlustes (da in-place).

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

Variante 3.a (halbrekursiv)
Typ alternativ
Eigenschaften halbrekursiv, in-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(nlogn)
Vergleiche n(logn-1.1) n(logn-1.1) n(logn-0.7)
Vertauschungen 0 n n

avlsort(field A, int l, int r) {
  root:= new node(l);
  for i:=l+1 to r do {
    root:= insert(A, root, new node(i));
  }
  for i:= l to r do {
    B[0][i] = i;
    B[1][i] = i;
  }
  resolve(A, B, l, root);
}

node insert(field A, node current, node element) {
  ...
}

int resolve(field A, int[][] B, int index, node current) {
  if (current <> null) then {
    index:= resolve(A, B, index, current.left);
    s:= B[0][current.index];
    t:= B[1][index];
    exchange(A[s], A[index]);
    B[0][t]:= s;
    B[1][s]:= t;
    index++;
    return resolve(A, B, index, current.right);
  } else {
    return index;
  }
}

node rrot(node a) {
  ...
}

node lrot(node a) {
  ...
}

node balance(node a, int bal) {
  ...
}

class node {
  ...
}


Avlsort, Variante 3