Siemax - Software Entwicklung,  Swapsort-Sortieralgorithmus

Kapitel III:

Swap-Sort als Interface für andere effiziente Sortieralgorithmen und/oder Mischverfahren

Betrachtet man einfaches Swap-Sort:

Swap-Sort(a[],f,l) {
         if(f<l) {
                   // Aufteilung - Phase 1
                   k=f+(l-f)/2;                // Aufteilung des Problems in kleinere Teile
                   // wenn die 2 Teilarrays nicht stabil sortiert werden, ist i.a. die gesamte
                   // Sortierung nicht mehr stabil
                   sortiere a[] von Index f bis Index k    // sortiert 1. Teil des Problems
                   sortiere a[] von Index k+1 bis Index 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
         }}

Man erkennt hier, daß es gar nicht vonnöten ist Swap-Sort() rekursiv aufzurufen, sondern man kann hier jeden beliebigen anderen Sortieralgorithmus verwenden. Ist der hierbei verwendete Sortieralgorithmus allerdings nicht stabil, dann ist i.a. eine stabile Sortierung nicht mehr gegeben. Dies könnte man z.B. einsetzen um den schlechtesten Fall von QuickSort zu verbessern. QuickSort benötigt im schlechtesten Fall ~ c*n*n Vergleiche, Phase 1 von Swap-Sort benötigt bei Anwendung von QuickSort im schlechtesten Fall ~ c*(n/2)*(n/2)*2 Vergleiche. Will man den schlechtesten Fall von QuickSort noch weiter verringern, teilt man durch rekursiven Aufruf von Swap-Sort das Problem solange, bis das Teilproblem klein genug ist.

Da QuickSort ein Sortierverfahren ist, welches selbst das Gesamtsortierproblem in weitere Unteraufgaben aufteilt, kann man QuickSort und Swap-Sort z.B. (mittels indirekter Rekursion) so kombinieren, daß QuickSort die Unteraufgaben Swap-Sort lösen läßt und Swap-Sort alle Sortierunteraufgaben QuickSort lösen läßt.
 
Auch beim Mischen von Swap-Sort kann man andere Mischalgorithmen verwenden. Insbesondere kann man durch Auswahl eines geeigneten Mischverfahrens weiter optimieren. Die einzelnen Swap-Sort Algorithmen unterscheiden sich eigentlich durch ihre Verschiedenartigkeit beim Mischen.

MergeOfSwap-Sort(a[],i,j,k,l){
n=Calculate_n(a[],i,j,k,l);
if (!n--){// 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) { // mischt Teil 1 mit Teil 3
                   // verwende ein geeignetes Mischverfahren
                   // mische stabil, falls die Sortierung stabil sein soll
                   mische a[] von Index i bis Index j-n-1 mit a[] von Index j-n bis Index j
         }
         if(l!=k+n) { // mischt  Teil 2 mit Teil 4
                   // verwende ein geeignetes Mischverfahren
                   // mische stabil, falls die Sortierung stabil sein soll
                   mische a[] von Index k bis k+n mit a[] von Index k+n+1 bis Index l
         }}}
 

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