Stoogesort

Stooge sort (også Trippelsort ) er en rekursiv sorteringsalgoritme i henhold til prinsippet om deling og styre ( dele og erobre ).

prinsipp

• Hvis det første og det siste elementet ikke er i riktig rekkefølge, byttes de.
• Hvis det er mer enn to elementer i listen, fortsett, ellers avbryt.
• Sorter de to første tredjedeler av listen
• Sorter de to siste tredjedeler av listen
• Sorter de to første tredjedeler av listen

kompleksitet

Algoritmen vil være veldig dårlig i forhold til andre sorteringsalgoritmer, i datavitenskap er dette med Landau symbol ved uttrykt. Siden til og med Bubblesort har bedre kjøretid, er Stoogesort bare av interesse for illustrasjonsformål. ${\ displaystyle O (n ^ {\ log _ {1 {,} 5} {3}}) \ approx O (n ^ {2.71})}$

Pseudokode

Følgende pseudokode sorterer inngangsmengden i stigende rekkefølge.

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

gjennomføring

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

Bevis på korrekthet

Bevis ved fullstendig induksjon (linjenumre refererer til pseudokoden gitt ovenfor): Induksjonsstart

For lengden på matrisen n = 1 og n = 2, sorterer Stoogesort riktig, siden elementene i listen er satt i riktig rekkefølge i algoritmens linje 1–4 og algoritmen avsluttes på dette punktet.

Induksjon lukking

Det følger av induksjonsantakelsen at samtalene i linje 6–8 returnerer riktig sorterte underarrayer. Elementer i den tredje tredjedelen av en korrekt sortering av matrisen kalles type _i- elementer, i = 1,2,3.

Etter å ha sortert de to første tredjedelene i linje 6, er det ikke lenger noe Type _3- element i den første tredjedelen av listen.

Etter å ha sortert de to siste tredjedeler i linje 7, inneholder den siste tredjedelen av listen alle type _3- elementer i sortert rekkefølge.

Etter å ha sortert de to første tredjedelene igjen i linje 8, er alle type _1- og type _2- elementene nå i sortert rekkefølge.

Se også

• Liste over algoritmer

weblenker

• Trippel sortering på Sortieralgorithmen.de