Stoogesort
# Stoogesort

Stooge sort (auch Trippelsort) ist ein rekursiver Sortieralgorithmus nach dem Prinzip Teile und herrsche (divide and 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 $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.

## 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$_3$-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$_3$-Elemente in sortierter Reihenfolge.
Nach der erneuten Sortierung der ersten zwei Drittel in Zeile 8 stehen jetzt außerdem alle Typ$_1$- und Typ$_2$-Elemente in sortierter Reihenfolge.