Heapsort, Variante 3 (trinär)

Hierbei handelt es sich um eine alternative verbesserte Variante. Die Idee folgt aus der Bemerkung zu Variante 1.

Variante 3.a (iterativ)
Typ standard, trinär (3-när)
Eigenschaften iterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n) Θ(nlogn) Ο(nlogn)
Vergleiche 4n n(1.9logn-2.4) 1.9nlogn
Vertauschungen n nlogn/1.6 nlogn/1.2

heapsort(field A, int l, int r) {
  buildheap(A, l, r);
  for i:=r downto l+1 do {
    exchange(A[l], A[i]);
    heapify(A, l, l, i-1);
  }    
}

buildheap(field A, int l, int r) {
  for i:= (r-l-1) div 3 downto 0 do {
    heapify(A, l, l+i, r);
  }
}

heapify(field A, int l, int q, int r) {
  for ever do {
    largest:= l+3*(q-l)+1;
    if (largest <= r) then {
      p:= largest+1;
      if (p <= r) and (A[p] > A[largest]) then {
        largest:= p;
      }
      if (p < r) and (A[p+1] > A[largest]) then {
        largest:= p+1;
      }
      if (A[largest] > A[q]) then {
        exchange(A[largest], A[q]);
        q:= largest;
      } else {
        return;
      }
    } else {
      return;
    }
  }
}

Variante 2.b (halbiterativ)
Typ standard, trinär (3-när)
Eigenschaften halbiterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(logn) Ο(logn)
Laufzeit Ω(n) Θ(nlogn) Ο(nlogn)
Vergleiche 4n n(1.9logn-2.4) 1.9nlogn
Vertauschungen n nlogn/1.6 nlogn/1.2

heapsort(field A, int l, int r) {
  buildheap(A, l, r);
  for i:=r downto l+1 do {
    exchange(A[l], A[i]);
    heapify(A, l, l, i-1);
  }    
}

buildheap(field A, int l, int r) {
  for i:= (r-l-1) div 2 downto 0 do {
    heapify(A, l, l+i, r);
  }
}

heapify(field A, int l, int q, int r) {
  largest:= l+3*(q-l)+1;
  if (largest <= r) then {
    p:= largest+1;
    if (p <= r) and (A[p] > A[largest]) then {
      largest:= p;
    }
    if (p < r) and (A[p+1] > A[largest]) then {
      largest:= p+1;
    }
    if (A[largest] > A[q]) then {
      exchange(A[largest], A[q]);
      heapify(A, l, largest, r);
    }
  }
}


Heapsort, Variante 3