Kurs:Algorithmen und Datenstrukturen/Vorlesung/Sortieren2 Verteiltes Sortieren

Aus Wikiversity




Verteiltes Sortieren[Bearbeiten]

Auf dieser Seite wird das verteilte Sortieren behandelt. Eine Laufzeit von n log n für Sortieren ist sehr effizient für viele Anwendungen. Das häufige Sortieren großer Mengen von Elementen kann dennoch ein Problem sein, durch häufige Festplattenzugriffe. Die Ausnutzung paralleler Hardware kann den Sortierprozess beschleunigen. Algorithmen wie MergeSort bieten sich zur Verteilung an, doch das Problem ist, dass der Merge-Schritt nicht direkt parallelisierbar ist. Wir schauen uns verteiltes Sortieren exemplarisch am BatcherSort-Algorithmus an.

Batcher Sort Idee[Bearbeiten]

Hier ist die grundsätzliche Idee wie bei MergeSort. Das Array wird in zwei gleich große Teilarrays geteilt und es wird rekursiv mit jedem Teilarray fortgefahren und sortiert. Anschließend werden die resultierenden Teilarrays gemischt. Der Merge-Schritt wird jedoch bei BatcherSort auch rekursiv durchgeführt.

Beispiel[Bearbeiten]

  • Sei I eine Liste mit Elementen 1,...,n
9 2 5 1 8 7 3 6
  • Sortiere die Elemente 1,...,n/2 und n/2+1,...,n
1 2 5 9 3 6 7 8
  • Sortiere die Elemente 1,3,5,...,n-1 und 2,4,6,...,n
1 2 3 6 5 8 7 9
  • Vergleiche und vertausche die Elemente 2/3,4/5,6/7
1 2 3 5 6 7 8 9
  • Nun ist die Liste sortiert.

Wir nehmen an, dass Listen eine Länge für natürliche Zahlen N haben.

Algorithmus[Bearbeiten]

void batcherSort(int[] list){
   batcherSort(list, 0, list.length-1);
}

void batcherSort(int[] list, int u, int o){
   if(u==o) return;

   //diese beiden Zeilen können parallel ausgeführt werden
   batcherSort(list, u, (u+o)/2);
   batcherSort(list, (u+o)/2+1,o);
   merge(list,u,o,1);
}
void merge(int[] list, int u, int o, int d){
   if(2*d>=o-u)
       compare(list,u,u+d);
   else{

      //diese beiden Zeilen können parallel ausgeführt werden
      merge(list, u, o, 2*d);
      merge(list, u+d, o, 2*d);
      for(int i = u+d; i <= o-d; i += 2*d)
         compare(list, i, i+d);
   } 
}

void compare(int[] list, int k, int l){
   if(list[k] > list[l]){
      int b = list[k];
      list[k] = list[l];
      list[l] = b;
}}

Die Sortierphase ist ähnlich wie bei MergeSort.

Analyse[Bearbeiten]

Theorem der Terminierung[Bearbeiten]

Das Theorem der Terminierung besagt, dass der Algorithmus BatcherSort für jede Eingabe int[]f nach endlicher Zeit terminiert.

Beweis[Bearbeiten]

Alle rekursiven Aufrufe erhalten stets eine echt  kleinere Eingabe und terminieren bei einer  einelementigen Eingabe. 

Theorem der Korrektheit[Bearbeiten]

Der Algorithmus BatcherSort sortiert ein Array f korrekt. 

Theorem der Laufzeit[Bearbeiten]

Der Algorithmus BatcherSort hat bei sequentieller Abarbeitung  eine Laufzeit von .

Der Algorithmus BatcherSort hat bei paralleler Abarbeitung eine  Laufzeit von 


Discussion