ここでは、最も基本的なソートアルゴリズムである「挿入ソート」について解説します。
まずはこの動画をご覧ください。挿入ソートのイメージがつかめると思います。
解説
早速、挿入ソートのアルゴリズムについて解説していきます。
方針
ここでは、数列「3 1 4 5 2 8 6 7」ををソートして、「1 2 3 4 5 6 7 8」にすることを目指しています。
方針としては、下のように、まずは１つ目の値をソート済みにする、次に１つ目と２つ目の値をソート済みに、次に１つ目と２つ目と３つ目の値をソート済みに、、、というように、ソート済みの数列の範囲を増やしていきます。
緑がソート前、青がソート済みの数列です。ソート済みの範囲がどんどん広がっていき、最終的にすべての値がソート済みになることがわかりますね。
青を左手、緑を右手にあるトランプだと考えるとわかりやすいかもしれません。
ソート前の右手のトランプから１枚ずつ選んで、ソート済みの左手のトランプの適切な位置に挿入することで、ソートを実現するわけです。
具体的な処理
冒頭の動画の、１つ１つのスライドで起こっていることを見ていきましょう。
先ほど、青がソート済みであるといいました。ソート前の数列のうち、１つ目の値（３）は、何の処理も行わずにソート済みとみなすことができます。
ですから、下のようになります。
ここからが挿入ソートのスタートです。
ソート前の数列（緑）の次の値は１です。これをKeyとして保持します。
この値をソート済みの数列のどこに挿入すればいいのかを特定します。
まず、Keyの１つ左の値と比べます。すると、Keyは３より小さいことがわかります。
したがって、Keyは３よりも左に位置するはずです。
トランプをしている人間であれば、３の左にそのまま挿入できます。しかし、コンピュータではそうできるとは限りませんから、工夫が必要です。
そこで、まず比較対象となっている値（灰色の３）を１つ右にも格納します。
１はKeyとして保持していますから、１つ右が上書きされても問題ありません。
そして、比較対象の３の部分に１を格納するのです。
こうすることで、無事に最初の２つの値をソート済みにすることができました。
以降の値についても、それぞれ同様の処理を行うことで、ソートを実現することができます。
Pythonで実装
挿入ソート（insert sort）をPythonで実装する場合、下のようなコードになります。
上の説明よりも、むしろわかりやすいかもしれません。
def insert_sort(seq):
for i in range(1,len(seq)):
key = seq[i]
j = i-1
while (j >= 0) and (seq[j] > key):
seq[j+1] = seq[j]
j -= 1
seq[j+1] = key
return seq
コメント