Slowsort

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[1] vorgestellt.

Inhaltsverzeichnis

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:

  • (1.1) Bestimme das Maximum der ersten Hälfte des zu sortierenden Feldes: Wähle das letzte Element der (rekursiv) sortierten ersten Hälfte.
  • (1.2) Bestimme das Maximum der zweiten Hälfte des zu sortierenden Feldes: Wähle das letzte Element der (rekursiv) sortierten zweiten Hälfte.
  • (1.3) 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 := (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 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 ε > 0. Der Algorithmus ist daher nicht polynomial. 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 < = i < j < = 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 n2 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


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Walsersort — Slowsort (von engl. slow: langsam) oder auch Walsersort ist ein langsamer, rekursiver, stabiler Sortieralgorithmus, der nach dem Prinzip Vervielfache und kapituliere (engl. Multiply and surrender, eine Parodie auf Teile und herrsche) arbeitet. Er …   Deutsch Wikipedia

  • Sortieralgorithmen — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Sortieralgorithmus — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Stabil (Sortierverfahren) — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

  • Stabiles Sortierverfahren — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

  • Bogosort — Class Sorting algorithm Data structure Array Worst case performance [1] Best case performance Ω …   Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Sortierverfahren — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von… …   Deutsch Wikipedia

  • Stabilität (Sortierverfahren) — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”