Stooge sort


Stooge sort

Stooge sort (auch Trippelsort) ist ein rekursiver Sortieralgorithmus nach dem Prinzip Teile und herrsche (divide and conquer).


Inhaltsverzeichnis

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

Komplexität

Der Algorithmus besitzt eine im Vergleich zu anderen Sortieralgorithmen sehr schlechte Worst-Case-Laufzeit, in der Informatik wird dies mittels Landau-Symbol durch 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 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] \leftrightarrow A[j]
3  if i+1 \ge j
4     then return
5  k \leftarrow\lfloor(j-i+1)/3\rfloor
6  stoogesort(A,i,j-k)  \quad \triangleright Sortieren der ersten zwei Drittel
7  stoogesort(A,i+k,j)  \quad \triangleright Sortieren der letzten zwei Drittel
8  stoogesort(A,i,j-k)  \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 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 Typi-Elemente, i=1,2,3.

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

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

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

Weblinks

Siehe auch: Liste von Algorithmen


Wikimedia Foundation.

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

  • Stooge sort — (Сортировка по частям[1], Блуждающая сортировка[2])  рекурсивный алгоритм сортировки с временной сложностью . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка… …   Википедия

  • Stooge sort — Infobox Algorithm class=Sorting algorithm data=Array time = O( n log(3)/log(1.5)) space = O( n ) optimal=NoStooge sort is a recursive sorting algorithm with a time complexity of about O( n 2.7).The exponent s exact value is log(3) / log(1.5) =… …   Wikipedia

  • Stooge — A stooge is generally defined as a person that is under the control of another. Being called a stooge is not a form of praise. Stooge can also sometimes be used to mean Idiot .what is stooge......is a donkey *Stooge (missile), an early surface to …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Cycle sort — Example of cycle sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance Θ(n2) …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia