Siemax - Software Entwicklung,  Swapsort-Sortieralgorithmus

Swap-Sort mit zyklischem Verschieben am Stack

Wenn man das Mischen beim einfachen Swap-Sort betrachtet, kann man festellen, daß sich die rekursiven Aufrufe beim Mischen als binärer Lösungsbaum darstellen lassen, wobei zuerst der Knoten (hier swappt man), dann der linke Teilbaum und dann der rechte Teilbaum bearbeitet wird. Nun wollen wir nicht mehr sofort swappen, sondern erst dann, wenn wir mindestens 1 Element an seinen richtigen Platz plazieren können, von wo dieses Element nicht mehr verschoben wird. Hierzu macht man folgende Umstellung im Lösungsbaum: Behandelt man einen Knoten, so legt man zuerst die Information auf einen verketteten Stack, welcher beschreibt, was vertauscht werden soll, dann löst man den linken Teilbaum, nachher holt man die nötige Information wieder vom Stack und swappen, wenn noch etwas zu vertauschen ist, alle Elemente bis zum 1. Element des Stacks hinauf und dann löst man den rechten Teilbaum. Zur Veranschaulichung betrachten wir folgenden Stapel:

 

Das 1. Element ist jenes, welches als erstes auf den Stack gelegt wurde. Das letzte Element jenes, welches als letztes Element auf den Stack gelegt wurde.

Der Bereich A wurde bereits vom linken Teilbaum vertauscht, der Bereich V ist im Knoten zu vertauschen, d.h. daß der rechte V-Bereich vom 1. Element des Stacks zum linken V-Bereich des Knotens wandert und alle linken V-Bereiche nach rechts wandern. Der Rest wird von den anderen noch zu bearbeitenden Knoten vertauscht.

MergeOfSimpleStackSwap-Sort(a[],i1,i2,j1,j2,Stack) {
         d=Calculate_Distance(a[],i1,i2,j1,j2,Stack);
         if (d--) {
                   push Swap-Bereich [i2-d,i2] und [j1,j1+d] auf den verketteten Stack
                   if (i1<i2-d) MergeOfSimpleStackSwap-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) MergeOfSimpleStackSwap-Sort(a[],j1,j1+d,j1+d+1,j2,Strack);
         }}

Da man nun erst vertauscht, wenn man mindestens 1 Element an seine richtige Postion setzen kann, muß man die Indizes bei der Berechnung der Größe d transformieren, sodaß bei einem jeweiligen Vergleich, die richtigen Elemente verglichen werden. Dazu braucht man aber nur das letzte Element des Stacks, falls vorhanden, betrachten und transformieren den Index nur, wenn er in diesem Swap-Bereich enthalten ist.

Der Stapel ist in diesem Verfahren nicht durch O(log(Anzahl der Stapelelemente begrenzt)).

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