概要
- Pythonでソートアルゴリズムを再発明してみるだけ
- 今回はシェルソートについて
- 参考サイトのサンプルコードをできるだけ見ずに実装する
- とりあえず昇順ソートのみの対応とする
シェルソートの概要
- 挿入ソートの改良版
- 離れた要素同士で比較、挿入を行うことで「だいたいソートされた状態」にし、その後挿入ソートと同等の処理を行って「完全にソートされた状態」にするみたいな感じ
- コムソートと同じアイデア
- データ数が多い場合は高速らしい
- 不安定ソート
基本的な手順
- ソート対象のリストのサイズをもとにギャップ（比較する要素同士の距離）を決める（2回目以降は前回のギャップをもとにする）
- 左端の要素を「ソート済み」とみなす（2回目以降は、左端からn+1離れた要素を「ソート済み」とする）
- 「ソート済み」要素からギャップ分離れた要素を「未ソート」とみなす
- ソート済み要素（の右端）と未ソート要素を比較し、大小関係が逆なら、未ソート要素をソート済み要素の中の適切な位置に挿入して「ソート済み」要素とする。大小関係が合っていれば、その位置のまま「ソート済み」要素とする
- 比較する要素両方をギャップ分右にずらしながら手順3〜4を繰り返す
- ギャップ分離れた要素が範囲外になるところまできたら2に戻る（最初の「ソート済み」要素が1つ右にずれる）
- さらにまたギャップ分離れた要素が範囲外になるところまできたら1に戻る（ギャップが小さくなる）
- ギャップが1まで減ったら、挿入ソートと同等の処理を行う。右端まで処理が終わったらソート完了
ソース
import random
def shell_sort(lst):
# ギャップ計算のための初期値
gap = len(lst)
# ループ継続のフラグ
# ギャップが1の場合の処理が終わったら処理全体を終わらせるために使う
is_continue = True
# ギャップを変えていくためのループ
while gap > 0 and is_continue:
gap = (gap - 1) // 3
if gap == 0:
# ギャップが1の場合の処理（挿入ソートと同じ）は絶対にやらないといけない
# そしてそれが終われば処理全体が終わり
gap = 1
is_continue = False
# 「ソート済み」要素を変えていくためのループ
# 「ソート済み」といってもコード上ではその概念は登場せず、ループカウンタのある時点の値より前が「ソート済み」ということになる
for i in range(0, len(lst)):
j = i
# 配列を走査するためのループ
while j + gap < len(lst):
# 大小関係が逆なので入れ替えが必要
if lst[j] > lst[j+gap]:
# 挿入位置を探すためのループ
for k in range(i, j+gap, gap):
if lst[k] > lst[j+gap]:
lst.insert(k, lst[j+gap])
del lst[j+gap+1]
j += gap
lst = list(range(10))
random.shuffle(lst)
print("ソート前: " + str(lst))
shell_sort(lst)
print("ソート後: " + str(lst))