Pythonでシェルソートを実装するプログラムの書き方

シェルソートとは

シェルソート（Shell Sort）は、挿入ソートを改良した整列アルゴリズムです。実装する際には、リストとその長さを引数として受け取る関数を定義します。この関数では、一定の間隔（ギャップ）ごとに抽出した部分リストに対して整列を行い、間隔を徐々に狭めながら処理を繰り返します。

まず最も大きな間隔から開始し、間隔だけ離れた要素同士を比較・交換していきます。この操作を、間隔が最小値になるまで繰り返すことで、リスト全体が完全に整列されます。すべての部分リストがこの手順で並べ替えられるため、最終的にソート済みの状態になります。

なお、Pythonのリストは異なるデータ型の値（整数、浮動小数点数、文字列など）を混在させて格納できる柔軟なデータ構造です。

サンプルコード

以下に、シェルソートの実装例を示します。

def shell_sort(my_list, list_len):
    interval = list_len // 2
    while interval > 0:
        for i in range(interval, list_len):
            temp = my_list[i]
            j = i
            while j >= interval and my_list[j - interval] > temp:
                my_list[j] = my_list[j - interval]
                j -= interval
            my_list[j] = temp
        interval //= 2

my_list = [ 45, 31, 62, 12, 89, 5, 9, 8]
list_len = len(my_list)
print ("The list before sorting is :")
print(my_list)
shell_sort(my_list, list_len)
print ("\nThe list after performing shell sorting is :")
print(my_list)

出力結果

The list before sorting is :
[45, 31, 62, 12, 89, 5, 9, 8]

The list after performing shell sorting is :
[5, 8, 9, 12, 31, 45, 62, 89]

コードの解説

• 「shell_sort」という名前の関数を定義し、リスト本体とその長さを引数として受け取ります。
• 変数「interval」は「//」演算子を使って初期化されます。これはフロア除算（切り捨て除算）を行う演算子です。
• フロア除算により、値は小数点以下が切り捨てられた最も近い整数に丸められます。
• リストを走査しながら、比較対象となる要素を一時変数「temp」に退避させます。
• interval 以上のインデックスを持つ各要素について、interval 分だけ前方にある要素と値を比較し、順序が崩れている場合は後方へずらしていきます。
• 1回の処理が完了するたびに、interval を再びフロア除算して間隔を半分に縮小します。
• メイン部分ではリストを定義し、ソート前の状態をコンソールに表示します。
• リストとその長さを引数として渡し、shell_sort 関数を呼び出します。
• ソート後のリストがコンソールに出力され、昇順に整列されていることが確認できます。