Stoogesort

Stooge sort (also Trippelsort ) is a recursive sorting algorithm according to the principle of divide and rule ( divide and conquer ).

principle

• If the first and the last element are not in the correct order, they are swapped.
• If there are more than two elements in the list, continue, otherwise cancel.
• Sort the first two thirds of the list
• Sort the last two thirds of the list
• Sort the first two thirds of the list

complexity

The algorithm will be very poor in comparison to other sorting algorithms run time, in the computer science this is by Landau symbol by expressed. Since even Bubblesort has a better runtime behavior, Stoogesort is only of interest for viewing. ${\displaystyle O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})}$

Pseudocode

The following pseudocode sorts the input quantity in ascending order.

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

implementation

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

Proof of correctness

Proof by complete induction (line numbers refer to the pseudocode given above): Induction start

For the length of the array n = 1 and n = 2, Stoogesort sorts correctly, since the elements of the list are put in the correct order in lines 1–4 of the algorithm and the algorithm terminates at this point.

Induction closure

It follows from the induction assumption that the calls in lines 6-8 return correctly sorted subarrays. Elements in the ith third of a correct sorting of the array are called type _i elements, i = 1,2,3.

After sorting the first two thirds in line 6, there is no longer any Type ₃ element in the first third of the list.

After sorting the last two thirds in line 7, the last third of the list contains all type ₃ elements in sorted order.

After sorting the first two-thirds again in row 8, all type ₁ and type ₂ elements are now in sorted order.

See also

• List of algorithms

Web links

• Triple sort at Sortieralgorithmen.de