2011-10-07 95 views
0

臭皮匠排序是下面描述的排序算法:傀儡排序如何工作?

Stooge-Sort(A,i,j) 
if(A[i]>A[]]) 
    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) 

算法有一個可怕的運行時間,我知道。
問題:我想知道這個算法是如何工作的?

+1

'如果(A [I]> A []])'必須'如果(A [I]> A [j]])' – Gajahlemu

+1

只需用一個短陣列,一支鉛筆和一張紙「玩電腦」 - 找出代碼的最簡單方法就是在腦海中執行它(或者使用調試器和步驟,但是我有時依靠手工勞動的粉絲:) –

回答

3

您排序子數組的第一個和最後一個元素。 (如果需要交換)

然後你遞歸排序的第一個2/3 第三子陣的,子陣的最後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和完整的數組排序。

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