Siemax - Software Entwicklung,  Swapsort-Sortieralgorithmus

Swap-Sort mit zyklischem Verschieben

Swap-Sort mit zyklischen Verschieben baut auf dem einfachen Swap-Sort-Sortieralgorithmus auf, wobei das Mischen in abgeänderter Weise erfolgt, um die Verschiebungen und Vergleiche zu reduzieren. Aber wenn man es anders versucht benötigt man zusätzlichen Speicher. So werden wir jetzt eine spezielle Art zu mischen betrachten und dann diese mit dem einfachen Swap-Sort-Algorithmus kombinieren. Man wählt eine gewisse Zahl m. Diese Zahl ist die Maximalanzahl der Elemente, welche man direkt einfügt bzw. die Maximalanzahl sortierter Folgen, welche eingefügt wird.


Nun betrachtet man 2 Fallunterscheidungen, die 2 sortierte Arrays mischen.

linke Folge

rechte Folge

Teil 1

Teil 2

Teil 3

Teil 4

1. Fall: Man mischt Teil 2 mit Teil 4 von links nach rechts. Man vergleicht maximal m mal die kleinsten Elemente von Teil 2 und Teil 4 und nimmt das kleinere heraus und fügt es in einem neuen Teilarray ein.  

 

 

 

Rest von Teil 2

Rest von Teil 4

 

 

maximal m sortierte Elemente von Teil 2 und Teil 4. Diese Elemente sind <= jenen Elementen von den Resten des Teils 2 und Teils 4.

 

 

2. Fall: Man mischt Teil 1 mit Teil 3 von rechts nach links. Man vergleicht maximal m mal die größten Elemente von Teil 1 und Teil 3 und nimmt das größere heraus und fügt es in einem neuen Teilarray ein.

Rest von Teil 1

Rest von Teil 3

 

 

 

 

 

maximal m sortierte Elemente von Teil 1 und Teil 3. Diese Elemente sind >= jenen Elementen von den Resten des Teils 1 und Teils 3.

 

 

In jedem Fall generiert man ein Array mit zusätzlich maximal m Elementen an ihren korrekten Plätzen. Und die Reste der Elemente, welche noch nicht aussortiert wurden, mischt man erneut. Und somit hat man die Kombination mit einfachem Swap-Sort hergestellt.

Rest von Teil 1

Rest von Teil 3

aussortierte Elemente

Rest von Teil 2

Rest von Teil 4

wird neu gemischt

 

wird neu gemischt


Soeben wurde gezeigt, daß man durch Vorgabe einer Zahl m, bis zu 2*m Elemente direkt aussortieren und an die richtige Stelle setzen kann. Analoges gilt für sortierte Teilfolgen. In diesem Fall haben wir dann maximal 2*m Teilfolgen für die gilt: Alle Elemente einer Teilfolge mit Index i kleiner als Index j sind kleiner gleich jedem einzelnen Element der Teilfolge mit Index j.

Bei einfachen Swap-Sort haben wir die Elemente stets nur ausgetauscht.

Nun da man jetzt nicht mehr einfach wie bei einfachen Swap-Sort einen Speicherbereich einfach mit einem anderen austauscht, sondern einige Elemente beim Mischen gleich an ihren richtigen Plätzen einfügt, welche nicht mehr weiter gemischt werden, gibt es hier nicht nur einfache Zyklen. Wie z.B. den Zyklus 8, 6, 9, 7, 5, 8.



Beim zyklischen Verschieben rettet man ein Element vom Zyklus in einer Speichervariable. Dann hat man einen Platz, wo man ein Element hineinschreiben kann. Dann bewegt man jenes Element, das genau in diese Lücke gehört dorthin. Und dann hat man wieder eine freie Lücke. Diesen Vorgang kann man solange wiederholen bis man das gerettete Element an seinen richtigen Platz plazieren kann.




Aber um eine minimale Anzahl von Speicherbewegungen zu erhalten, soll man gerade das Vorhandensein solcher Zyklen ausnützen. Denn zyklisches Verschieben ist viel effizienter als einfach nur Austauschen.

Swap(a,b) { c=a; b=a; b=c; } // man benötigt 3 Zuweisungen um 2 Elemente auszutauschen!

Hat man einen Zyklus mit n Elementen so gilt hingegen: Die Anzahl der Zuweisungen, um zyklisch zu verschieben, beträgt n+1. Bei der Abarbeitung eines Zyklus verwendet man ein von[] Feld, welches die Positionen enthält, von wo ein Element herkopiert wird. Die Indizes des von[] Feldes sind verschoben, so daß das 1. Element in der Indexliste jenes Element ist, welches im Feld a[] das Element mit Position j ist.

Swap(a[],von[],,j) {v=a[j]; for(i=j,k=von[0];k!=j;i=k,k=von[k-j]) a[i]=a[k]; a[i]=v;} // von[] Indexliste des Zyklus

Für die Abarbeitung von einem Zyklus, wenn man Folgen aussortiert hat, verwendet noch zusätzlich ein nach[] Feld. Somit hat man die Position, wo man hineinkopieren kann. Man sieht, daß das nach[] Feld uns die Indizes des a[] Feldes liefert. Da a[nach[i]] bis a[nach[i+1]-1] einer sortierten Teilfolge entspricht, wenn das nach[] Feld sortiert wurde. Deshalb erstellen wir das nach[] Feld so, daß es in einer sortierten Reihenfolge vorliegt. Dies läßt sich auf natürliche Weise tun.

Swap(a[],von[],nach[],n) {                   // Abarbeitung für einen Zyklus aus der Verschiebungsliste
i=von[0]; l=k=nach[0]; d=a[k];             // rette erstes Element
do {   a[k]=a[i];                                 // verschiebe
         j=binary_search(nach[],0,n-1,i); // suche j, so daß nach[j]<=i<nach[j+1] gilt,
                                                       // bzw. nach[j]<=i, falls nach[j+1] nicht existiert
         k=i; i=von[j]+(i-nach[j]);             // berechne nächsten Index
} while (i!=l);                                      // wiederhole solange bis wir das gerettete Element
a[k]=d;}                                             // zurück schreiben können

Es könen auch mehrere Zyklen vorhanden sein. Dann wiederholt man die Abarbeitung solange bis alle Zyklen abgearbeitet wurden. Wie z. B. 5, 7, 5 dann 6, 10, 8, 6 dann 9, 11, 9.



Solche Zyklen lassen sich beim Mischen 2 sortierter Teilarrays immer dann finden, sofern man nicht einfach swappen (austauschen) muß oder alle Elemente des 2. Teilarrays bereits größer gleich jenen Elementen des 1. Teilarrays sind.

Kann man nur austauschen, tauscht man einfach Teil 2 mit Teil 3 aus. Andernfalls, falls man überhaupt noch etwas tun muß, verwendet man zyklisches Verschieben. Hat man die aussortierten Elemente bereits verschoben, kann in speziellen Fällen ein noch zu verschiebender Bereich übrigbleiben, falls dieser nicht schon in einem Zyklus hineinfällt oder man nicht noch zusätzlich einfache Zyklen hinzufügt, so daß diese abgearbeitet werden mußten. Wie z. B.:

 

 

Man sieht, wenn man den Zyklus 7, 4, 9, 13, 8, 12, 7 verschiebt, daß die Elemente an Position 6 und 11 noch nicht an ihre richtigen Plätze verschoben wurden. Dies passiert dann, wenn die Anzahl der Elemente von Teil 2 weniger der Anzahl aussortierter Elemente von Teil 1, Teil 2 und Teil 3 echt größer 0 ist und die Anzahl der aussortierten Elemente von Elemente von Teil 1 gleich der Anzahl der aussortierten Elemente von Teil 4 ist. In unserem Beispiel: (4 – (1+1+1))>0 und 1=1. Wenn man aussortierte Folgen statt Elemente verwendet, dann muß man in diesem Fall die Elemente der aussortierten Folgen zählen.

In der obigen Skizze wurden die Pfeile nur für die aussortierten Elemente bzw. Folgen angegeben. Dies hat einen guten Grund, dann alle Pfeile bzw. Verschiebungen die zu einem Zyklus gehören und nicht in den Bereich der aussortierten Elemente weisen bzw. kopieren, kann man auf einfache Weise berechnen. Z. B.: Hat man eine Position die echt kleiner als die linke Position der aussortierten Elemente ist, dann braucht man zu dieser Position nur die Anzahl der Elemente von Teil 3 und die Anzahl der aussortierten Elemente von Teil 1 addieren. D.i. in diesem Fall für die Position 4: (4+4+1)=9, also kopiert man a[4]=a[9]. Hat man hingegen eine Position die echt größer als die rechte Position der aussortierten Elemente ist, dann braucht man bei dieser Position nur die Anzahl der Elemente von Teil 2 und die Anzahl der aussortierten Elemente von Teil 4 subtrahieren. D.i. in diesem Fall für die Position 12: (12-(4+1))=7, also kopiert man a[12]=a[7]. Wiederum gilt: Wenn man aussortierte Folgen statt Elemente verwendet, dann muß man in diesem Fall die Elemente der aussortierten Folgen zählen.

Oben wurde erwähnt, wenn mehrere Zyklen vorhanden sind, so bearbeitet man jeden Zyklus bis alle abgearbeitet wurden. Wenn diese obige Skizze betrachtet wird, zeigt sich, daß wenn wir als Startelement für einen Zyklus die aussortierten Elemente nehmen, dann haben wir jeden Zyklus zumindest einmal durchlaufen.

linke Folge

rechte Folge

1. Teil

2. Teil

3. Teil

4. Teil

Reste von Teil 1 und 3

Aussortierte Elemente

Rest von Teil 4



Nun stellt sich die Frage: Ist es möglich mit weniger Startelementen für die Zyklen alle Zyklen zu durchlaufen, ohne jedes aussortierte Element auszuwählen? Dies ist in gewissen Fällen möglich. Wenn z. B. die aussortierten Elemente den Teil 2 oder den Teil 3 komplett ausfüllen. Dies ist deshalb, weil wenn z.B. der Teil 2 von aussortierten Elementen aufgefüllt wird, alle im Teil 2 vorhandenen Elemente nach Teil 3 und/oder Teil 4 verschoben werden. Da aber nun alle Elemente von Teil 2 bereits in der rechten Folge liegen und die rechte Folge nach der Verschiebung nur mehr Elemente von Teil 2 und Teil 4 enthalten darf, müssen auch alle Elemente, welche vorher in dem Teil 3 waren ebenfalls verschoben worden sein. Insbesondere müssen dann auch alle zu verschiebenden Elemente von Teil 1 betroffen sein.

Swap(von[],                    // Indexliste der Zyklen
         a1,a2,a3,a4,          // Anzahl der aussortierten Elemente von Teil 1, Teil 2, Teil 3 und Teil 4
         i1,i2,j1,j2)              // linke und rechte Position von Teil 2, linke und rechte Position von Teil 3
{
         l=a1+a3;              // Anzahl aussortierter Elemente, welche in den Teil 2 verschoben werden
         r=a2+a4;              // Anzahl aussortierter Elemente, welche in den Teil 3 verschoben werden
         len=l+r;                // Anzahl aussortierter Elemente
         low=j1-l;               // linke Position der aussortierten Elemente
         up=i2+r;                // rechte Position der aussortierten Elemente
         nil=low;
                                                                   // wähle die Startelemente der Zyklen:
         if (low<=i1) { len=l; k=i1-low; nil=i1; }       // Fall: alle aussortierten Elemente überdecken Teil 2
         else if (j2<=up) { k=l; len=j2-low+1; }       // Fall: alle aussortierten Elemente überdecken Teil 3
         else k=0;

         while (k<len)
         {         i=index=low+k; v=a[i];                  // rette Startelement des Zyklus
                   for(;;)
                   {
                           if(i<low) j=i+(j2-i2)+a1;        //addiere # El. von Teil 3 + # aussortierter El. von Teil 1
                           else if(i>up)j=i-(j1-i1+a4);   //subtrahiere (#El von Teil 2 +#aussortierter El von Teil 4)
                           else
                           {
                                     j=von[i-low];     //hole Index j für ein nach Position i zu verschiebenden Element
                                     von[i-low]=nil;   // markiere als besucht
                           }
                           if (j==index) break;   // wiederhole solange bis gerettetes Element
                                                           // zurückgeschrieben werden kann
                           a[i]=a[j]; i=j;            // verschiebe im Zyklus
                   }
                   a[i]=v;                                     // schreibe gerettetes Element zurück
                   while (++k<len && von[k]==nil); // überspringe schon bearbeitete Zyklen
         }
         // bearbeite alle noch offenen einfachen Zyklen
         if (i1+a2<=i2-l && a1==a4) Swap(i1+a2, i2-l, j1+r, j2-a3);
}

Im obigen Algorithmus kann man die Hauptschleife sogar noch früher verlassen, da man weiß, daß wenn alle aussortierten Elemente verschoben wurden, man die Schleife verlassen kann.

Beim Sortieren mit Folgen verwendet man 2 Felder von[] und nach[] gegenüber beim Sortieren von Elementen, welches nur ein zusätzliches Feld von[] benötigt. Weiters verwendet man beim zyklischen Verschieben, um den Index einer sortierten Folge zu berechnen, aus der man ein Element verschieben möchte, eine binäre Suchroutine. So betrachtet ist Swap-Sort mit sortierten Folgen gegenüber der Sortierung von Elementen i.a. erst dann effizienter, wenn das Array, daß zu sortieren vorliegt, nur leicht unsortiert ist.

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