Bitonicsort, Variante 1 (Original, depth first)

Hierbei handelt es sich um die Original-Variante. Sie liefert das typische Bild eines "depth first"-Algorithmus.

Für dieses Verfahren gibt es keine vollständig iterative Realisierung.

Variante 1.a (halbrekursiv)
Typ standard
Eigenschaften halbrekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(logn) Θ(logn) Ο(logn)
Laufzeit (p) Ω((logn)²) Θ((logn)²) Ο((logn)²)
Laufzeit Ω(n(logn)²) Θ(n(logn)²) Ο(n(logn)²)
Vergleiche n(logn)²/4 n(logn)²/4 n(logn)²/4
Vertauschungen 0 n(logn)²/8 n(logn)²/4

bitonicsort(field A, int l, int r) {
  bitonicsort(A, l, r, true);
}

bitonicsort(field A, int l, int r, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    do parallel {
      bitonicsort(A, l, q, true);
      bitonicsort(A, q+1, r, false);
    }
    bitonicmerge(A, l, r, asc);
  }
}
 
bitonicmerge(field A, int l, int r, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    k:= q-l+1;
    for i:= l to q do parallel {
      if ((A[i] > A[i+k]) = asc) then {
        exchange(A[i],A[i+k]);
      }
    }
    do parallel {
      bitonicmerge(A, l, q, asc);
      bitonicmerge(A, q+1, r, asc);
    }
  }
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(logn) Θ(logn) Ο(logn)
Laufzeit (p) Ω((logn)²) Θ((logn)²) Ο((logn)²)
Laufzeit Ω(n(logn)²) Θ(n(logn)²) Ο(n(logn)²)
Vergleiche n(logn)²/4 n(logn)²/4 n(logn)²/4
Vertauschungen ??? n(logn)²/8 n(logn)²/4

bitonicsort(field A, int l, int r) {
  bitonicsort(A, l, r, true);
}

bitonicsort(field A, int l, int r, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    do parallel {
      bitonicsort(A, l, q, true);
      bitonicsort(A, q+1, r, false);
    }
    bitonicmerge(A, l, r, asc);
  }
}
 
bitonicmerge(field A, int l, int r, bool dir) {
  if (l < r) then {
    q:= (l+r) div 2;
    comp(A, l, q, q-l+1, asc);
    do parallel {
      bitonicmerge(A, l, q, asc);
      bitonicmerge(A, q+1, r, asc);
    }
  }
}

comp(field A, int l, int r, int k, bool asc) {
  if (l < r) then {
    q:= (l+r) div 2;
    do parallel {
      comp(A, l  , q, k, asc);
      comp(A, q+1, r, k, asc);
    }
  } else {
    if ((A[l] > A[l+k]) = asc) then {
      exchange(A[l],A[l+k]);
    }
  }
}


Bitonicsort, Variante 1