Stoogesort

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

Principle

  • The first and the last element is not in the correct order, they are interchanged.
  • If more than two items in the list, continue, or 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 has a very poor compared to other sorting algorithms running time, in computer science, this is expressed by the Landau symbol by. Since even Bubblesort has a better runtime behavior, Stoogesort is to be illustrative only of interest.

Pseudocode

The following pseudo code sorts the input set in ascending order.

A: list (array ) with the unsorted input set i: Left limit of the array to be sorted Clippings j: Right limit of the array to be sorted Clippings stoogesort (A, i, j) 1 if A [i ]> A [ j] 2 then A [i ] A [ j] 3 if i 1 j 4 then return 5 k ( j -i 1 ) / 3 6 stoogesort (A, i, jk ) sorting the first two-thirds 7 stoogesort ( a, i k, j ) sorting the last two-thirds 8 stoogesort (A, i, jk ) sorting the first two-thirds implementation

Java

/ / Interface method ( to force the call with the correct starting values ​​) public void stoogeSort (int [ ] a) {    stoogeSort (a, 0, a.length ); }   / / Internal method private void stoogeSort (int [] a, int s, int e) {     if ( a [ e-1 ] 2)     {       int third = len / 3; / / Reminder: This is the ( rounded ) 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 field ( Left) > box (Right ) Then           Temp = array ( Left)           Field (Left ) = field ( Right)           Field ( 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 correctness proof

Proof by Mathematical Induction (line number refer to the above pseudo-code ): Induction Base

N = 1 and n = 2 sorted Stoogesort correct for length of the array, since the elements of the list are placed in the correct order on line 1-4 of the algorithm and the algorithm terminates at the site.

Induction conclusion

From the induction hypothesis follows that deliver the calls in lines 6-8 correctly sorted subarrays. Elements in the ith third of a correct sorting of the array hot Typical elements, i = 1,2,3.

After sorting, the first two-thirds in line 6 is no longer Typ3 element is in the first third of the list.

After sorting, the last two-thirds in line 7 all Type 3 elements are in the last third of the list in sorted order.

After re- ordering of the first two-thirds in line 8 now also available all type-1 and type-2 elements in sorted order.

Recursion List of algorithms
750689
de