Pythonヒルソート

ヒルソートは、インクリメンタルソートアルゴリズムとも呼ばれ、挿入ソートのより効率的で改善されたバージョンです。しかし、ヒルソートは不安定なソートアルゴリズムです。

ヒルソートの基本的な概念は、最初にソートされるレコードのシーケンス全体をいくつかのサブシーケンスに分割して直接挿入ソートを行い、シーケンス全体のレコードが「基本的に順序付けられている」場合、すべてのレコードに挿入ソートを順番に実行します。

実例

def shellSort(arr): 
  
    n = len(arr)
    gap = int(n/2)
  
    while gap > 0: 
  
        for i in range(gap,n): 
  
            temp = arr[i] 
            j = i 
            while  j >= gap and arr[j-gap] >temp: 
                arr[j] = arr[j-gap] 
                j -= gap 
            arr[j] = temp 
        gap = int(gap/2)
  
arr = [ 12, 34, 54, 2, 3] 
  
n = len(arr) 
print ("ソート前:") 
for i in range(n): 
    print(arr[i]), 
  
shellSort(arr) 

print ("\nソート後:") 
for i in range(n): 
    print(arr[i]),

上記のコードを実行した結果は次のとおりです。

ソート前:
12
34
54
2
3

ソート後:
2
3
12
34
54