Siemax - Software Entwicklung,  Swapsort-Sortieralgorithmus

Swap-Sort mit zyklischem Verschieben am durch log(n) Stapelelemente begrenzten Stack

Im vorherigen Kapitel haben wir ein Verfahen veschrieben, wo mittels eines Lösungsbaumes das Mischen von Swap-Sort lösen. Dabei hat man zuerst immer den linken vor dem rechten Teilbaum bearbeitet. Spiegelbildlich, wenn man stets den rechten vor dem linken Teilbaum bearbeitet, funktioniert das oben beschriebene Verfahren ebenso. Da wir die Höhe des Lösungsbaumes beschränken wollen, werden wir jenen Teilbaum zuerst bearbeiten, der das kleinere Teilproblem löst, und dann erst denn anderen. Da sich die einzelnen Swap-Bereiche nicht mehr so einfach überlagern, daß der rechte Swap-Bereich eines Knotens immer unter dem linken Swap-Bereichs eines übergeordeten Knotens, falls vorhanden, liegt (oder spiegelbildlich), müssen wir in diesem Verfahren eine aufwendigere Indexberechnung durchführen. Zur Veranschaulichung betrachten wir dieses Stufenmodel:


  

Man sieht, daß man hier am Stack wie bereits vorher beschrieben zyklisches Verschieben anwenden kann.

MergeOfStackSwap-Sort(a[],i1,i2,j1,j2,Stack) { for (;;) {
(*)        d=Calculate_Distance(i1,i2,j1,j2,Stack);
           if (!d--) break;
           push Swap-Bereich [i2-d,i2] und [j1,j1+d] auf den verketteten Stack
           if (i2-i1<=j2-j1) // kleineres Teilproblem zuerst => Stack = O(log n)
           {
                     if (i1+d<i2) MergeOfStackSwap-Sort(a[],i1,i2-d-1,i2-d,i2,Stack);

(**)                 vertausche noch zu vertauschende Elemente am Stack, so daß das letzte Element am Stack
                     keine mehr zu vertauschenden Elemente enthält

                     pop Swap-Bereich vom verketteten Stack // [i2-d,i2] und [j1,j1+d] wurden vertauscht
                     if (j1+d==j2) break;
                     i1=j1, j1+=d, i2=j1, j1++;
           }
           else
           {
                     if (j1+d<j2) MergeOfStackSwap-Sort(a[],j1,j1+d,j1+d+1,j2,Stack);

(**)                 vertausche noch zu vertauschende Elemente am Stack, so daß das letzte Element am Stack
                     keine mehr zu vertauschenden Elemente enthält

                     pop Swap-Bereich vom verketteten Stack // [i2-d,i2] und [j1,j1+d] wurden vertauscht
                     if (i1+d==i2) break;
                     j2=i2, i2-=d, j1=i2, i2--;
           }}}

Die Indizes, die man in der obigen Funktion verwendet, zeigen i.a. nicht mehr auf die eigentlichen Daten, die verschoben werden sollen und müssen in den Programmteilen (*) und (**) übersetzt werden. Dabei sucht man den noch nicht übersetzten Index vom letzten Stackelement hinauf – sagen wir es so: Man steigt die Stiege die Stufen hinauf -, bis man diesen in einem Swap-Bereich findet. Nun testet man, ob er sich in einem bereits als vertauscht markierten Teil des Swap-Bereiches befindet, dann braucht man den Index nicht mehr übersetzen. Andernfalls gibt es zwei Fallunterscheidungen:

1. Der Index befindet sich im linken Teil eines Swap-Bereiches: Dann übersetzt man den Index auf dieser Stufe, so daß der Index nun das andere zu vertauschende Element im rechten Teil des Swap-Bereiches indiziert.
2. Der Index befindet sich im rechten Teil eines Swap-Bereiches: Dann übersetzet man den Index auf dieser Stufe, so daß der Index nun das andere zu vertauschende Element im linken Teil des Swap-Bereiches indiziert.
 

Haben wir den Index in dieser Stufe übersetzt, gehen wir die Stiege hinauf und prüfen, ob der Index weiter übersetzt werden muß, usf.

Im Teil (**) ist es nicht einmal notwendig alle Elemente, welche vertauscht wurden als vertauscht zu markieren, sondern nur jene, welche sich unmittelbar vor dem letzten Stackelement befinden. Das erspart einiges an Buchführung.
 

zurück zur Inhaltseite von Swap-Sort, dem effizienten Sortier-Algorithmus