Как работает сортировка марионеток?

Question

Сортировка по Stooge - это алгоритм сортировки, описанный ниже:

Stooge-Sort(A,i,j)
if(A[i]>A[j]])
  then exchange(A[i],A[j])
if i+1>=j 
  then return
k = [(j-i+1)/3]
Stooge-Sort(A,i,j-k)
Stooge-Sort(A,i+k,j)
Stooge-Sort(A,i,j-k)

Алгоритм работает ужасно, и я знаю это.
Вопрос: Я хочу знать, какэтот алгоритм работает?

Answer 1

Вы сортируете первый и последний элемент вашего подмассива.(Поменяйте местами при необходимости)

Затем вы рекурсивно сортируете первые 2/3 ^rd подмассива, последние 2/3 ^rd подмассива и снова первые 2/3 ^rd подмассива.

Для доказательства правильности вы можете использовать индукцию.

1. Clearly this algo works for 0, 1 and 2 element array.
2. Assuming it works for all arrays shorter than subarray
   [i, j] let's prove it works for array[i,j] also. Let's
   divide range[i,j] in 3 parts x, y and z;
    a. After Stooge-Sort(A,i,j-k), or [xy], every element in range
       y are larger than that of x. (Because range [xy] has
       lesser elements than range[i,j])
    b. After Stooge-Sort(A,i+k,j), or [yz], all largest elements
       have moved to z and are sorted. So z is sorted and contains
       largest elements of the array.
    c. After Stooge-Sort(A,i,j-k), or [xy], first (2/3)rd part of
       array is also sorted making the complete array sorted.

Из шагов a, b и c мы можем заключить части x, y и zотсортированы, и все элементы x больше (или равны), чем y, а все элементы z (больше или равны), чем z, и что весь массив отсортирован.

Answer 2

Использует тактику «разделяй и властвуй».

Set i = list first element index , j = list last element index
Set list item at position i = min(list value at position i, list value at position j)
Set list item at position j = max(list value at position i, list value at position j)
If (j - i) <= 1 return sorted list 
Else Set t = (j - i + 1) / 3 
Call sort with {i = i, j = j - t} then {i = i + t, j = j } then {i = i, j = j - t}

Допустим, я хочу отсортировать массив [1,4,5,3,-6,3,7,10,-2,-5], эта сортировка начнется:

Before: [1,4,5,3,-6,3,7,10,-2,-5] (i=0 ;j=9)
Before: [-5,4,5,3,-6,3,7,10,-2,1] (i=0 ;j=6)
Before: [-5,4,5,3,-6,3,7,10,-2,1] (i=0 ;j=4)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=3)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=2)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=2)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=1 ;j=3)
Before: [-6,3,5,4,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,5,4,-5,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,3,5,4,-5,3,7,10,-2,1] (i=2 ;j=3)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=2 ;j=3)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=3)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=2)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=3)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=4)
Before: [-6,-5,4,5,3,3,7,10,-2,1] (i=1 ;j=3)
Before: [-6,-5,4,5,3,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,-5,4,5,3,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,-5,4,5,3,3,7,10,-2,1] (i=2 ;j=3)
//etc