Siemax - Software Entwicklung,  Swapsort-Sortieralgorithmus

Vorwort

In diesem Artikel präsentiere ich einen mir bis dato nicht vorgekommenen Sortieralgorithmus, ich nenne ihn Swap-Sort, der außerordentlich effizient ist und dazu noch stabil sortiert. Ein Algorithmus sortiert stabil, wenn bei Gleichheit der Schlüssel zweier Elemente, die Reihenfolge der Elemente nicht verändert wird.

Da es eine technisch komplizierte Materie ist, habe ich mich sehr bemüht die Erkenntnisse genau darzulegen. Ich verwende auch eine C-ähnliche Syntax zur Beschreibung von algorithmischen Abläufen, wobei aber alles Wesentliche auch in den Kommentaren oder im Text steht.

In der Geschichte der Entwicklung von Sortieralgorithmen gab es zuerst 2 gut bekannte Sortieralgorithmen für lineare Felder, bekannt als BubbleSort (Sortieren durch Vertauschen) und SortByStraightInsertion (Sortieren durch Einfügen), welche einen Speicherbereich O(n) und eine Zeitkomplexität von O(n2) beanspruchen. Ein anderer Algorithmus bekannt als MergeSort (Sortieren durch Mischen) verwendet einen Speicherbereich von O(n), hat aber eine Zeitkomplexität von O(n log(n)).

Swap-Sort ist ein Algorithmus, der n Elemente auf einen Computer oder in einer Apparatur, sowie in den obengenannten bekannten Algorithmen sortiert, nur mit dem entscheidenden Unterschied, daß er mit zusätzlichen verwendeten Speicher sparsam umgeht und i.a. schneller abläuft, da er weniger Bearbeitungsschritte ausführt.

Zuerst werde ich zeigen, daß dieser Algorithmus eine Verbesserung der oben erwähnten Algorithmen ist.

BubbleSort ist einfach. Wir nehmen 2 benachbarte Elemente, vergleichen sie und tauschen sie aus, falls das 2. Element kleiner als das 1. ist. In C-ähnlicher Syntax, wobei a[] ein lineares Feld von a[0] bis a[n-1] ist:

do for(b=0,i=1;i<n;i++) if (a[i]<a[i-1]) { v=a[i]; a[i]=a[i-1]; a[i-1]=v; b=1; } while(b); // BubbleSort

Dieser Algorithmus hat einen außerordentlichen Nachteil, man muß das Array (=lineares Feld) solange durchlaufen bis keine Vertauschungen mehr durchgeführt werden. Seine Verbesserung SortByStraightInsertion vergleicht 2 benachbarte Elemente und falls das 2. Element kleiner als das 1. ist, dann bewegt es sich solange nach vorne, so daß alle Elemente bei denen es sich vorbei bewegte größer als dieses Element sind und alle Elemente vor diesem Element kleiner oder gleich diesem Element sind. In C-ähnlicher Syntax:

for(i=1;i<n;i++) if (a[i]<a[i-1]) { for(j=i-1;j&&(a[i]<a[j-1]);j--); v=a[i]; for(k=i;k>j;k--) a[k]=a[k-1]; a[j]=v; }

Nun verbessert man diesen Algorithmus noch einmal. Es gibt in diesem viel zu viele unnotwendige Speicherbewegungen von links nach rechts. Es würde viel besser sein, wenn man mehr als ein Element auf den richtigen Platz plazieren könnte. In diesem Fall sammelt man mehr als ein Element und stellt dieses in einem Durchgang an die richtigen Plätze. Man kann dies tun, in dem man auch den rechten Teil des Arrays sortiert. Dann nämlich kennt man alle Elemente vom rechten Teil, welche man im linken Teil des Arrays einfügen kann. Das sind zumindest alle Elemente, die kleiner als das größte Element des 1. Teilarrays sind. Und dann kann man  alle einzufügenden Elemente in einem einzigen Durchgang oder auch in mehreren Durchgängen einfügen. In C-ähnlicher Syntax:

for(i=1;i<n;i++) if(a[i]<a[i-1]) { // jetzt ist a[0] bis a[i-1] bereits sortiert
       Sort(a[],i,n-1);               // sortiert Teilarray von a[i] bis a[n-1]
       Merge(a[],0,i-1,i,n-1); // mische 2 sortierte Teilarrays, indem wir alle Elemente des 2. Teiles des Arrays
break; }                           // mit a[j]<a[i-1],j=i,...,n-1 in dem 1. Teil des Arrays einfügen

Da das Sortieren des 2. Teilarrays i.a. noch sehr aufwendig ist, lösen wir die Gesamtsortieraufgabe durch Aufteilung in kleinere Teilprobleme wie z.B.:

SubOfSort(a[],f,k,l) {
for(i=f;i<l && a[i+01]>a[i];i++);        // erzeugt ein sortiertes Teilarray von a[f] bis a[i]
(*)    for(;i<k;i=j) {                          // hier ist a[f] bis a[i] bereits sortiert
             j=((l-(i+01))<i-f)?l:i+(i-f)+01;
(**)       j=SubOfSort(a[i],i+01,j,l);  // sortiert Teilarray von a[i+1] bis a[j]
(***)      Merge(a[],f,i,i+01,j); }        // mischt 2 benachbarte sortierte Teilarrays
return i; }

Sort(a[],f,l) { SubOfSort(a[],f,l,l); }
Oder so:

Sort(a[],f,l) { if (f<l) { k=f+(l-f)/2;        // teile in mindestens 2 Teilarrays
(*)        Sort(a[],f,k);                      // gibt ein sortiertes Teilarrays zurück
(**)       Sort(a[],k+01,l);                 // gibt noch ein weiteres sortiertes Teilarray zurück
(***)      Merge(a[],f,k,k+01,l); }}     // mischt 2 benachbarte sortierte Teilarrays

Nun sieht man, daß ein Spezialfall dieser Verbesserung – nämlich wenn alle im 1. Teilarray einzufügenden Elemente vom 2. Teilarray in einem Durchgang im 1. Teilarray eingefügt werden – dem Sortieralgorithmus MergeSort entspricht. MergeSort leistet in den Schritten (*) bis (**) das selbe, welches der vorhergehende Algorithmus ebenfalls tut. Er teilt das lineare Array in 2 sortierte Teile. Aber MergeSort mischt in Schritt (***) die sortierten Teile des Arrays auf eine sehr aufwendige Art, indem es ein zusätzliches Array verwendet.
In C-ähnlicher Syntax:

MergeOfMergeSort(a[],f,k,j,l) { i=f, m=0;
         while(i<=k)
                 if (a[i]<=a[j]) if (m==0) i++,f++; else z[m++]=a[i++];
                 else { z[m++]=a[j]; if (j++==l) break; }
         if (i<=k) for(;i<=k;i++,m++) z[m]=a[i];               // mische alles in ein zusätzliches lineares Feld z[]
         for(j=0;j<m;j++) a[f++]=z[j]; }                           // kopiere m Elemente vom linearen Feld z[] zurück

Vorher wurde das Mischen folgendermaßen beschrieben: 2 sortierte Teilarrays mischt man, indem man alle Elemente des 2. Teilarrays, welche kleiner sind als das größte Element des 1. Teilarrays (aus dem 2. Teilarray entfernen) und in das 1. Teilarray einfügt. Bisher haben wir implizit angenommen, wenn wir 1 oder mehrere Elemente vom 2. Teilarray entfernen, so sind es stets die kleinsten Elemente und stehen somit im sortierten Teilarray auf der linken Seite, d.h. das Teilarray verkleinert sich somit indem man den untersten Index um die Anzahl der entnommenen Elemente erhöht. Hat man Elemente aus dem 2. Teilarray entnommen, so hat man Platz geschaffen, um das 1. Teilarray um genau die Anzahl der im 2. Teilarray entnommenen Elemente vergrößern zu können. D.h. man kann die aus dem 2. Teilarray entnommenen Elemente im 1. Teilarray einfügen. Dies kann man auf eine spezielle Art machen, indem man nicht wie üblich von vorne nach hinten bzw. von links nach rechts, sondern andersherum mischt, d.h. man vergleicht zuerst die hinteren dann die vorderen Elemente bzw. zuerst die rechten dann die linken Elemente. Und so kann man die entstandenen Leerplätze auf natürliche Weise auffüllen. Nun wird klar, daß man bei dieser Art von Mischen die Speichergröße, die man verwenden will, fest beschränken kann. Hat man nicht genug Speicher, um alle aus dem 2. Teilarray einzufügenden Elemente, in das 1. Teilarray mischen zu können, dann kann man den Vorgang solange wiederholen, bis man alle Elemente eingefügt hat. Man kann bei dieser Vorgehensweise des Mischens verallgemeinern, daß der Zeitaufwand beim Sortieren steigt, wenn wir weniger Speicherplatz zur Verfügung stellen.

Nun kann man diese Art des Mischens nochmals verbessern, so daß wir einen sehr leistungsfähigen Sortieralgorithmus erhalten, der bis auf einen Stack von O(log(n)) keinen zusätzlichen Speicher benötigt. Dazu wollen wir zuerst den oben beschriebenen Algorithmus anders formulieren. Wir können auch sagen: Wir mischen 2 sortierte Teilarrays, indem wir alle Elemente des 2. Teilarrays, welche kleiner sind als das größte Element des 1. Teilarrays, aus dem 2. Teilarray entfernen und mit dem 1. Teilarray im 1. Teilarray mischen. Nun bisher haben wir angenommen, daß sich die Größe eines Teilarrays noch verändern darf. Jetzt nehmen wir an, daß sich die Größe eines Teilarrays nicht mehr verändert. Dann sieht es so aus: Man mischt das 1. und das 2. sortierte Teilarray ins 1. Teilarray und mischt dann die übriggebliebenen Elemente des 1. und 2. Teilarrays ins 2. Teilarray. Egal ob man die Größe eines Arrays verändern läßt oder nicht, wir erhalten jedesmal ein sortiertes Array. Nur mit einem wesentlichen Unterschied: Man hat 1 Mischproblem in 2 Mischprobleme aufgeteilt. Und hat man erst mehrere Mischprobleme, so unterteilt man sie wieder weiter auf, solange bis man kein Mischproblem mehr aufteilen kann bzw. aufteilen braucht, da das zugehörige Teilarray bereits sortiert ist. Und nun könnte man fragen, wo bleibt hier eigentlich das Mischen, wenn man immer nur neue Mischprobleme erzeugt und zerkleinert, bis es nicht mehr nötig ist, ein sortiertes Array weiter zu unterteilen? Daher nenne ich diesen Algorithmus auch Swap-Sort, denn die Hauptaufgabe beim Aufteilen in neue Mischprobleme ist das Austauschen und zyklische Verschieben von Speicherbereichen.
 
 

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