Wikiversity

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Verteiltes Sortieren

< Kurs:Algorithmen und Datenstrukturen | Vorlesung


Startseite
Vorlesung

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.

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;
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{
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

Es gibt Unterschiede zu MergeSort. Zum einen ist der Merge-Schritt auch rekursiv definiert, zum anderen kann auch parallel bearbeitet werden. Der Aufwand bei linearer Abarbeitung ist n log n und somit schlechter als andere Sortierverfahren Der Aufwand bei paralleler Abarbeitung ist  

     

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Verteiltes_Sortieren&oldid=629089“