【基本情報技術者試験】シェルソートをPythonで実装

前回に引き続きソートアルゴリズムをPythonで実装していきます。今回は選択ソートを扱います。

1. 基本交換法（バブルソート）
2. 基本選択法（選択ソート）
3. 基本挿入法（挿入ソート）
4. シェルソート←今回の対象
5. クイックソート
6. マージソート
7. ヒープソート

シェルソートとは？

シェルソートとは配列の中である間隔ごとに要素をグループ化し挿入ソートを行い、その間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムのことです。
この間隔の決め方によって、シェルソートの実行時間は変わります。
今回は間隔の決め方は2の累乗（2ⁿ, 2^n-1, ・・・, 8, 4, 2, 1）とした場合について取り扱います。
アルゴリズムの概略としては下記のようになります。

1. 間隔hを決める（例えば上記の方法でやる場合には2ⁿ）
2. 間隔hで取り出したグループごとに挿入ソートを行う
3. 間隔hを狭める（2^n-1）
4. 間隔hが1となるまで2と3を繰り返す
5. 間隔hが1となったら全体の配列に対して挿入ソートを行う

例えば8, 3, 1, 2, 7, 5, 6, 4という数列があったときに下記のように更新していきます。（赤字部分が固定箇所になります。）

① 8, 3, 1, 2, 7, 5, 6, 4 （間隔を4としてグループ化）
② 7, 3, 1, 2, 8, 5, 6, 4 （グループごとに挿入ソートを行う。黄色のグループのみ順番が異なっているのでソートされる）
③ 7, 3, 1, 2, 8, 5, 6, 4 （間隔を2としてグループ化）
④ 1, 2, 6, 3, 7, 4, 8, 5 （グループごとに挿入ソートを行う。黄色と赤色それぞれのグループでソートされている）
⑤ 1, 2, 6, 3, 7, 4, 8, 5 （間隔が1となるので、挿入ソートを行う）
⑥ 1, 2, 3, 4, 5, 6, 7, 8 （間隔が1となるので、挿入ソートを行う）

実際のPythonのコードは下記になります。

listNum = [8, 3, 1, 2, 7, 5, 6, 4]
listNum

[8, 3, 1, 2, 7, 5, 6, 4]

lenNum = len(listNum)
h = lenNum // 2
while h > 0:
  for i in range(h, lenNum):
    j = i
    tmp = listNum[i]
    while listNum[j - h] > tmp and j >= h: 
      listNum[j] = listNum[j - h]
      j -= h
      listNum[j] = tmp

  h = h // 2
  print(listNum)

[7, 3, 1, 2, 8, 5, 6, 4]
[1, 2, 6, 3, 7, 4, 8, 5]
[1, 2, 3, 4, 5, 6, 7, 8]

シェルソートについては以上となります。
次回はクイックソートについて扱います。