侏儒排序

侏儒排序
使用侏儒排序法對一列數字進行排序的過程
概況
類別	排序演算法
資料結構	陣列
複雜度
平均時間複雜度	$O(n^{2})$
最壞時間複雜度	$O(n^{2})$
最佳時間複雜度	$\Omega (n)$
空間複雜度	$O(1)$輔助空間
最佳解	No
相關變數的定義

侏儒排序（英語：Gnome Sort）或愚人排序（英語：Stupid Sort）是一種排序演算法，最初在2000年由伊朗電腦工程師哈米德·薩爾巴齊-阿扎德（Hamid Sarbazi-Azad，謝里夫理工大學電腦工程教授）提出，他稱之為「愚人排序」。此後迪克·格魯納也描述了這一演算法，稱其為「侏儒排序」。此演算法類似於插入排序，但是移動元素到它該去的位置是通過一系列類似泡沫排序的移動實現的。從概念上講侏儒排序非常簡單，甚至不需要巢狀迴圈。它的平均執行時間是 $O(n^{2})$ ，如果列表已經排序好則只需 $O(n)$ 的執行時間。

解釋 

下面是侏儒排序的偽代碼，其中使用的陣列是下標從零開始的：

procedure gnomeSort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1

樣例 

給定一個未排序的陣列a = [5, 3, 2, 4]，侏儒排序在while迴圈中執行以下步驟。粗體表示pos變數當前所指的元素。

當前陣列	下一步操作
[5, 3, 2, 4]	a[pos] < a[pos-1]，交換
[3, 5, 2, 4]	a[pos] >= a[pos-1]，pos自增
[3, 5, 2, 4]	a[pos] < a[pos-1]，交換；pos > 1，pos自減
[3, 2, 5, 4]	a[pos] < a[pos-1]，交換；pos <= 1，pos自增
[2, 3, 5, 4]	a[pos] >= a[pos-1]，pos自增
[2, 3, 5, 4]	a[pos] < a[pos-1]，交換；pos > 1，pos自減
[2, 3, 4, 5]	a[pos] >= a[pos-1]，pos自增
[2, 3, 4, 5]	a[pos] >= a[pos-1]，pos自增
[2, 3, 4, 5]	pos == length(a)，完成

實作範例

Julia (程式語言)

# Julia Sample : GnomeSort

function GnomeSort(A)
	pos = 1
	while pos<length(A)+1
		if (pos==1) || (A[pos]>=A[pos-1])
			pos+=1
		else
			A[pos],A[pos-1] = A[pos-1],A[pos] 
			pos-=1
		end
	end
	return A
end

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

外部連結 

• 侏儒排序 （頁面存檔備份，存於互聯網檔案館）