侏儒排序

侏儒排序(英語:Gnome Sort)或愚人排序(英語:Stupid Sort)是一種排序算法,最初在2000年由伊朗計算機工程師哈米德·薩爾巴齊-阿扎德(Hamid Sarbazi-Azad,謝里夫理工大學計算機工程教授)提出,他稱之為「愚人排序」[1]。此後迪克·格魯納英語Dick Grune也描述了這一算法,稱其為「侏儒排序」[2]。此算法類似於插入排序,但是移動元素到它該去的位置是通過一系列類似冒泡排序的移動實現的。從概念上講侏儒排序非常簡單,甚至不需要嵌套循環。它的平均運行時間 ,如果列表已經排序好則只需 的運行時間。[3]

侏儒排序
使用侏儒排序法對一列數字進行排序的過程
概況
類別排序算法
資料結構數組
複雜度
平均時間複雜度
最壞時間複雜度
最優時間複雜度
空間複雜度輔助空間
最佳解No
相關變量的定義

解釋 

下面是侏儒排序的偽代碼,其中使用的數組是下標從零開始的

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 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

參考文獻

  1. ^ Sarbazi-Azad, Hamid. Stupid Sort: A new sorting algorithm (PDF). Newsletter (Computing Science Department, Univ. of Glasgow). 2 October 2000, (599): 4 [25 November 2014]. (原始內容存檔 (PDF)於2012-03-07). 
  2. ^ Gnome Sort - The Simplest Sort Algorithm. Dickgrune.com. 2000-10-02 [2017-07-20]. (原始內容存檔於2017-08-31). 
  3. ^ Paul E. Black. gnome sort. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. [2011-08-20]. (原始內容存檔於2011-08-11). 

外部連結