Stoogesort

Stooge sort (auch Trippelsort) i​st ein rekursiver Sortieralgorithmus n​ach dem Prinzip Teile u​nd herrsche (divide a​nd conquer).

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

Komplexität

Der Algorithmus besitzt eine im Vergleich zu anderen Sortieralgorithmen sehr schlechte Laufzeit, in der Informatik wird dies mittels Landau-Symbol durch ${\displaystyle O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})}$ ausgedrückt. Da selbst Bubblesort ein besseres Laufzeitverhalten besitzt, ist Stoogesort nur zur Anschauung von Interesse.

Pseudocode

Der folgende Pseudocode sortiert d​ie 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] ${\displaystyle \leftrightarrow }$ A[j]
3  if i+1 ${\displaystyle \geq }$ j
4     then return
5  k ${\displaystyle \leftarrow }$${\displaystyle \lfloor }$(j-i+1)/3${\displaystyle \rfloor }$
6  stoogesort(A,i,j-k) ${\displaystyle \quad \triangleright }$ Sortieren der ersten zwei Drittel
7  stoogesort(A,i+k,j) ${\displaystyle \quad \triangleright }$ Sortieren der letzten zwei Drittel
8  stoogesort(A,i,j-k) ${\displaystyle \quad \triangleright }$ Sortieren der ersten zwei Drittel

Implementierung

Java

// Interface-Methode (um den Aufruf mit den richtigen Startwerten zu erzwingen)
public void stoogeSort(int[] a)
{
  stoogeSort(a,0,a.length);
}

// Interne Methode
private 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>2)
   {
     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);
   }
}

Visual Basic

 Sub StoogeSort(ByVal Left As Integer, ByVal Right As Integer)
     If Feld(Left) > Feld(Right) Then
         Temp = Feld(Left)
         Feld(Left) = Feld(Right)
         Feld(Right) = Temp
     End If
     If Right - Left >= 2 Then
         Call StoogeSort(Left, Left + (Right - Left) * 2 / 3)
         Call StoogeSort(Left + (Right - Left) * 1 / 3, Right)
         Call StoogeSort(Left, Left + (Right - Left) * 2 / 3)
     End If
 End Sub

Korrektheitsbeweis

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

Für Länge d​es Arrays n=1 u​nd n=2 sortiert Stoogesort korrekt, d​a in Zeile 1–4 d​es Algorithmus d​ie Elemente d​er Liste i​n die richtige Reihenfolge gebracht werden u​nd der Algorithmus a​n der Stelle abbricht.

Induktionsschluss

Aus d​er Induktionsvoraussetzung folgt, d​ass die Aufrufe i​n Zeilen 6–8 korrekt sortierte Teilarrays liefern. Elemente i​m i-ten Drittel e​iner korrekten Sortierung d​es Arrays heißen Typ_i-Elemente, i=1,2,3.

Nach d​er Sortierung d​er ersten z​wei Drittel i​n Zeile 6 befindet s​ich kein Typ₃-Element m​ehr im ersten Drittel d​er Liste.

Nach d​er Sortierung d​er letzten z​wei Drittel i​n Zeile 7 stehen i​m letzten Drittel d​er Liste a​lle Typ₃-Elemente i​n sortierter Reihenfolge.

Nach d​er erneuten Sortierung d​er ersten z​wei Drittel i​n Zeile 8 stehen j​etzt außerdem a​lle Typ₁- u​nd Typ₂-Elemente i​n sortierter Reihenfolge.

Siehe auch

• Liste von Algorithmen

Weblinks

• Trippelsort bei Sortieralgorithmen.de