Stoogesort

Stooge sort ist ein rekursiver Sortieralgorithmus nach dem Divide-and-Conquer-Verfahren.

Inhaltsverzeichnis

1 Prinzip

2 Komplexität

Prinzip

Sind das erste und das letzte Element nicht in der richtigen Reihenfolge, so werden sie vertauscht.
Sind mehr als zwei Elemente in der Liste, fortsetzen, ansonsten abbrechen.
Sortiere die ersten zwei Drittel der Liste
Sortiere die letzten zwei Drittel der Liste
Sortiere die ersten zwei Drittel der Liste erneut

Komplexität

Der Algorithmus besitzt eine im Vergleich zu anderen Sortieralgorithmen sehr schlechte Worst-Case-Laufzeit, Informatiker notieren dies mittels Landau-Symbol durch O(n^2.7). Der exakte Wert des Exponenten ist log(3)/log(1.5).

Pseudocode

Der folgende Pseudocode sortiert die Eingabemenge aufsteigend.


 A: Liste (Array) mit der unsortierten Eingabemenge
 i: Linke Grenze des zu sortierenden Ausschnitts des Arrays
 j: Rechte Grenze des zu sortierenden Ausschnitts des Arrays
 
 stoogesort(A,i,j)
 1  if A[i] > A[j]
 2     then A[i]  A[j]
 3  if i+1  j
 4     then return
 5  k (j-i+1)/3
 6  stoogesort(A,i,j-k)  Sortieren der ersten zwei Drittel
 7  stoogesort(A,i+k,j)  Sortieren der letzten zwei Drittel
 8  stoogesort(A,i,j-k)  Sortieren der ersten zwei Drittel

Implementierung

Eine Umsetzung des Algorithmus in Java:

 // Interface-Methode (um den Aufruf mit den richtigen Startwerten zu erzwingen)
 void stoogeSort(int[] a)
 {
   stoogeSort(a,0,a.length);
 }
 
 // Interne Methode
 void stoogeSort(int[] a,int s,int e)
 {
    if(a[e-1]<a[s])
    {
      int temp=a[s];
      a[s]=a[e-1];
      a[e-1]=temp;
    }
    int len=e-s;
    if(len>1)
    {
      int third=len/3;   // Zur Erinnerung: Dies ist die (abgerundete) Integer-Division
      stoogeSort(a,s,e-third);
      stoogeSort(a,s+third,e);
      stoogeSort(a,s,e-third);
    }
 }

Korrektheitsbeweis

Beweis durch Vollständige Induktion (Zeilennummer beziehen sich auf den oben angegebenen Pseudocode): Induktionsanfang

Für Länge des Arrays n=1 und n=2 sortiert Stoogesort korrekt, da in Zeile 1-4 des Algorithmus die Elemente der Liste in die richtige Reihenfolge gebracht werden und der Algorithmus an der Stelle abbricht.

Induktionsschluss

Aus der Induktionsvoraussetzung folgt, dass die Aufrufe in Zeilen 6-8 korrekt sortierte Teilarrays liefern. Elemente im i-ten Drittel einer korrekten Sortierung des Arrays heißen Typ_i-Elemente, i=1,2,3.

Nach der Sortierung der ersten zwei Drittel in Zeile 6 befindet sich kein Typ₃-Element mehr im ersten Drittel der Liste.

Nach der Sortierung der letzten zwei Drittel in Zeile 7 stehen im letzten Drittel der Liste alle Typ₃-Elemente in sortierter Reihenfolge.

Nach der erneuten Sortierung der ersten zwei Drittel in Zeile 8 stehen jetzt außerdem alle Typ₁- und Typ₂-Elemente in sortierter Reihenfolge.

Weblinks

Everything2.com - Stooge sort

Siehe auch: Liste von Algorithmen