Stabile Swap-Sort Sortieralgorithmen
1. Einfaches Swap-Sort
Einfaches Swap-Sort läßt sich in 3 verschiedene Phasen unterteilen Aufteilung der Sortieraufgabe in kleinere Subsortieraufgaben, anschließendem Swappen (Austauschen von Speicherbereichen) und erneutem Mischen der sortierten Teilfolgen. Für jede einzelne Phase bietet sich das Programmierparadigma divide & conquer (teile und beherrsche) an. D.h. jede Phase kann durch Aufteilen auf kleinere Probleme und anschließendem Lösen der Teilprobleme gelöst werden. Die 1. Phase ist selbst lediglich nur eine Problemaufteilung.
Swap-Sort(a[],f,l) {
if(f<l) {
// Aufteilung - Phase 1 oder Vorsortierphase
k=f+(l-f)/2; // Aufteilung des Problems in kleinere Teile
Swap-Sort(a[],f,k); // sortiert 1. Teil des Problems
Swap-Sort(a[],k+1,l); // sortiert 2. Teil des Problems
// MergeOfSwap-Sort() swappt (Phase 2) und mischt (Phase 3)
MergeOfSwap-Sort(a[],f,k,k+1,l); // mischen zweier sortierter Arrays
}}
MergeOfSwap-Sort() mischt, die in der Aufteilungsphase generierten Teilprobleme. Es verwendet folgendes Problemaufteilungsverfahren: Zwei sortierte Teilfolgen einer Folge werden so miteinander gemischt, daß man eine genau zu berechnende Zahl n von Elementen einer Teilfolge, die letzten n Elemente der 1. Teilfolge sowie die ersten n Elemente der 2. Teilfolge, miteinander austauscht (swappt), so daß nachher alle Elemente der 2. Teilfolge größer oder gleich der 1. Teilfolge sind. Mischt man dann die verbliebenen Elemente der 1. Teilfolge mit den neu hinzugefügten und die verbliebenen Elemente der 2. Teilfolge mit den neu hinzugefügten, dann erhalten wir 2 sortierte Teilfolgen, wobei die 2. Teilfolge ausschließlich Elemente enthält, die größer oder gleich aller Elemente der 1. Teilfolge sind, und somit ist bei Aneinanderreihung der 1. und der 2. Teilfolge die Gesamtfolge sortiert.
|
Zur Veranschaulichung teilen wir ein Array in 4 Teile.
Gesamtfolge
|
entspricht der 1. Sortierten Teilfolge
|
entspricht der 2. sortierten Teilfolge
|
|
|
|
|
|
Es gibt exakt n Elemente in diesen Teil des Arrays, jedes Element in diesem Teil ist >= als jedes Element von Teil 1 und > als jedes Element von Teil 3.
|
Es gibt exakt n Elemente in diesem Teil des Arrays, jedes Element in diesem Teil ist < als jedes Element von Teil 2 und <= als jedes Element von Teil 4.
|
|
Die Zahl n >= 0 läßt sich exakt berechnen:
Calculate_n(a[],a1,a2,b1,b2) {
n=0; do if (a[a2]>a[b1]) n++; else break; while (a1!=a2-- && b1++!=b2);
return n;}
Da es bei dieser Berechnung sehr auf die Effizienz ankommt, verwenden wir hier ein Berechnungsverfahren, welches mit ca. log(Minimum(Anzahl der Elemente einer der beiden Teilfolgen)) Berechnungsschritten auskommt:
Calculate_n(a[],a1,a2,b1,b2){ // berechnet wie viele Elemente eingefügt werden sollen mittels
// eines Verfahrens, welches auf Intervallteilung beruht
u=0; if (a2-a1<b2-b1) o=a2-a1; else o=b2-b1; o++; // Zuweisung der Intervallgrenzen
do{
n=u+(o-u)/2; // Intervallhalbierung
if (a[a2-n]<=a[b1+n]) o=n; else u=++n; // Einengung des Intervalls
}
while (u!=o); // Schleifenabbruch, wenn die Zahl n bestimmt wurde
return n; }
Wir nehmen nun alle n Elemente von Teil 3 und mischen diese Elemente mit Teil 1 und dann nehmen wir alle n Elemente von Teil 2 und mischen diese Elemente mit Teil 4. Dann erhalten wir ein sortiertes Array:
MergeOfSwap-Sort(a[],i,j,k,l){
n=Calculate_n(a[],i,j,k,l); // berechnet wie viele Elemente ausgetauscht werden sollen
// = Anzahl der Elemente von Teil 2 bzw. Teil 3
if (!n--){ // nur wenn noch nicht sortiert, tue =>
// n wird der Effizenz wegen um 1 reduziert
// Austauschen Phase 2
Swap(a[],j-n,j,k,k+n); // swap (tausche aus) Teil 2 mit Teil 3
// Mischen Phase 3
if(i!=j-n) MergeOfSwap-Sort (a[],i,j-n-1,j-n,j); // mischt Teil 1 mit Teil 3
if(l!=k+n) MergeOfSwap-Sort (a[],k,k+n,k+n+1,l); // mischt Teil 2 mit Teil 4
}}
Wie man sieht, wird das Mischen (Phase 3) durch rekursives Teilen des Problems gelöst. Für das Swappen (Phase 2 - Austauschen) des Speicherbereiches ist eine Aufteilung in Subaufgaben erst auf Multiprozessorsystemen sinnvoll. Da der Stack (auch Stapelspeicher genannt = Speicher der lokalen Variablen und Rücksprungadressen) beim Mischen, so klein wie möglich sein soll, um einen Überlauf zu verhindern, werden wir diesen auf log(Anzahl der Elemente der Gesamtfolge) Stapelelemente beschränken, indem wir das kleinere Teilproblem zuerst lösen und dann für das andere Teilproblem keinen neuen Funktionsaufruf durchführen, sondern in der selben Funktion bleiben, indem wir die Argumente der Funktion neu belegen und zur 1. Anweisung des Funktionskörpers zurückkehren.
MergeOfSwap-Sort(a[],i,j,k,l){ for(;;) { // Endlosschleife
n=Calculate_n(a[],i,j,k,l);
if (!n--){
Swap(a[],j-n,j,k,k+n);
// Mischen Phase 3
if (j-i<=l-k) { // löse kleineres Teilproblem zuerst
// Array von i bis j ist kleineres Teilproblem
if(i!=j-n) MergeOfSwap-Sort (a[],i,j-n-1,j-n,j); // mischt Teil 1 mit Teil 3
if (k+n==l) break; // Schleifenabbruch
i=k, k+=n, j=k, k++; // setze Argumente der Funktion neu
// ein erneuter Aufruf der Funktion mit den neu gesetzten
// Argumenten würde Teil 2 mit Teil 4 mischen, deshalb
// gehe zum Anfang zurück
} else {
// Array von k bis l ist kleineres Teilproblem
if(l!=k+n) MergeOfSwap-Sort (a[],k,k+n,k+n+1,l); // mischt Teil 2 mit Teil 4
if (i+n==j) break; // Schleifenabbruch
l=j, j-=n, k=j, j--; // setze Argumente der Funktion neu
// ein erneuter Aufruf der Funktion mit den neu gesetzten
// Argumenten würde Teil 1 mit Teil 3 mischen, deshalb
// gehe zum Anfang zurück
}}}}
|