Jumpsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Erstetzt man in dieser Variante alle Vertauschungen durch Verschiebungen, so erhält man die Variante 4 von Bubblesort. Dementsprechend können alle Optimierungen bzgl. dieser Variante auch hier angewendet werden.

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

jumpsort(field A, int l, int r) {
  for i:= r downto l+1 do {
    q:= l;
    for j:= l to i-1 do {
      if (A[j+1] > A[q]) then {
        exchange(A[q], A[j]);
        q:= j+1;
      }
    }
    exchange(A[q], A[i]);
  }
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n²/12 n²/2

jumpsort(field A, int l, int r) {
  if (l < r) then {
    jump(A, l, l, r);
    jumpsort(A, l, r-1);
  }
}

jump(field A, int q, int l, int r) {
  if (l < r) then {
    if (A[l+1] > A[q]) then {
      exchange(A[q], A[l]);
      q:= l+1;
    }
    jump(A, q, l+1, r);
  } else {
    exchange(A[q], A[r]);
  }
}


Jumpsort, Variante 1