臭皮匠排序

臭皮匠排序
使用臭皮匠排序為一列數字進行排序的過程
概況
類別	排序演算法
資料結構	數組
複雜度
最壞時間複雜度	$O(n^{\frac {\log 3}{\log 1.5}})$
空間複雜度	$O(n)$
最佳解	No
相關變數的定義

臭皮匠排序（英語：Stooge Sort）是一種採用分治法的低效排序演算法，甚至慢於泡沫排序。在《演算法導論》第二版第7章（快速排序）的思考題中被提到，是由Howard、Fine等教授提出的所謂「漂亮的」排序演算法。

該演算法得名於三個臭皮匠，每個臭皮匠都能暴打其他兩個，其他兩個也會卯起來扁其中一個。

實現

• 如果最後一個值小於第一個值，則交換這兩個數
• 如果當前集合元素數量大於等於3：

1. 使用臭皮匠排序法排序前2/3的元素
2. 使用臭皮匠排序法排序後2/3的元素
3. 再次使用臭皮匠排序法排序前2/3的元素

 algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if (j - i + 1) >= 3 then
         t = (j - i + 1) / 3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

實作範例

Julia

# Julia Sample : Stooge Sort

function StoogeSort(A,v1,v2)

	if A[v1]>A[v2]
		A[v1],A[v2] = A[v2],A[v1]
	end
	
	if (v2-v1+1)>2
		t = Int(round((v2-v1+1)/3))
				
		StoogeSort(A, v1  , v2-t)
        StoogeSort(A, v1+t, v2  )
        StoogeSort(A, v1  , v2-t)
	end
	return A
end


# Main Code
A = [16,586,1,31,354,43,3]
println(A)                           # Original Array
println(StoogeSort(A,1,length(A)))   # Stooge Sort Array

參考

• Black, Paul E. stooge sort. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. [2011-06-18]. （原始內容存檔於2008-09-20）. 
• Everything2.com – Stooge sort （頁面存檔備份，存於互聯網檔案館）
• Sorting Algorithms（包含臭皮匠排序） （頁面存檔備份，存於互聯網檔案館）
• Stooge sort – implementation and comparison （頁面存檔備份，存於互聯網檔案館）