Slowsort

Slowsort (von engl. slow: langsam) ist ein langsamer, rekursiver Sortieralgorithmus, der nach dem Prinzip Vervielfache und kapituliere (engl. Multiply and surrender, eine Parodie auf Teile und herrsche) arbeitet. Er wurde 1986 von Andrei Broder und Jorge Stolfi in ihrer (nicht ganz ernst gemeinten) Veröffentlichung Pessimal Algorithms and Simplexity Analysis vorgestellt.

Prinzip

Slowsort ist ein rekursiver Algorithmus, der in folgenden Schritten arbeitet:

1. Bestimme das Maximum des zu sortierenden Feldes und platziere es an dessen Ende.
2. Sortiere das restliche Feld, durch einen rekursiven Aufruf des Algorithmus selbst.

Dabei wird der erste Schritt nach dem Prinzip Vervielfache und kapituliere in mehrere geringfügig einfachere Schritte unterteilt:

• Bestimme das Maximum der ersten Hälfte des zu sortierenden Feldes: Wähle das letzte Element der (rekursiv) sortierten ersten Hälfte.
• Bestimme das Maximum der zweiten Hälfte des zu sortierenden Feldes: Wähle das letzte Element der (rekursiv) sortierten zweiten Hälfte.
• Bestimme das Maximum der beiden Teilmaxima.

Dies wird rekursiv wiederholt, bis das Teilfeld nur noch ein einziges Element enthält und die Lösung somit nicht weiter hinausgezögert werden kann.

 procedure slowsort(A,i,j)                            // Sortiert das Array A[i],...,A[j]
   if i >= j then return
   m := floor((i+j)/2)                                // abrunden, falls i+j ungerade
   slowsort(A,i,m)                                    // (1.1)
   slowsort(A,m+1,j)                                  // (1.2)
   if A[j] < A[m] then vertausche A[j] und A[m]       // (1.3)
   slowsort(A,i,j-1)                                  // (2)

Die ersten fünf Zeilen vom Pseudocode unterscheiden sich dabei nicht von Mergesort, und nur das Vereinigen der beiden sortierten Teilfelder geschieht (anstelle eines effizienten Mischens) durch einen extrem ineffizienten rekursiven Aufruf.

Die Korrektheit lässt sich relativ einfach durch vollständige Induktion über die Anzahl der Elemente zeigen.

Des Weiteren ist Slowsort kein stabiles Sortierverfahren: Bei der Eingabe (1, 3, 2a, 2b) wird auf der ersten Rekursionsstufe 3 mit 2b vertauscht. Im weiteren Verlauf findet dann keine weitere Vertauschung mehr statt, so dass Slowsort mit der Ausgabe (1, 2b, 2a, 3) terminiert.

Komplexität

Die Laufzeit $T(n)$ für Slowsort genügt der Rekursionsgleichung $T(n)=2T(n/2)+T(n-1)+1$. Eine untere asymptotische Grenze für $T(n)$ ausgedrückt in der Landau-Notation ist $\Omega \left(n^{\frac {\log _{2}(n)}{(2+\epsilon )}}\right)$ für ein beliebiges $\epsilon >0$. Der Algorithmus ist daher nicht polynomiell. Slowsort ist somit auch im best case ineffizienter als z. B. Bubblesort mit einer Komplexität von ${\mathcal {O}}(n^{2})$.

Anzahl an Vertauschungen

Im Gegensatz dazu benötigt Bubblesort mindestens so viele Vertauschungen wie Slowsort. Ein Maß, wie „stark“ ein Feld $A$ mit $n$ Elementen sich von dem sortierten Feld unterscheidet, ist die Anzahl an Fehlständen, also die Anzahl Paare $(i,j)$ mit $1\leq i<j\leq n$ für die $A[i]>A[j]$ gilt.

Bei einem Tausch bei Bubblesort vermindert sich die Anzahl der Fehlstände um genau eins, während sie sich bei Slowsort um mindestens eins (um genau eins, falls alle Werte im Feld verschieden sind) verringert. Die Anzahl an Fehlständen ist daher eine obere Schranke für die Anzahl an Vertauschungen von Slowsort, da genau ein sortiertes Feld keine Fehlstände hat. Die maximale Anzahl an Vertauschungen bei einem Feld mit $n$ Elementen beträgt bei Slowsort daher maximal $\textstyle {\binom {n}{2}}$ und zwar genau dann, wenn es absteigend sortiert ist. Innerhalb eines rekursiven Aufrufes findet deshalb nur in den seltensten Fällen überhaupt eine Vertauschung statt.

Weblinks

• Wissenschaftliche Veröffentlichung von Broder und Stolfi