挿入ソート

主なアルゴリズムの一つとしてソートがある。
ソートは、ファイリングキャビネットの中のすべてのファイルを割り当てられた番号もしくは記号順に昇順もしくは降順でならびかえることを考えるとわかりやすい。以下、番号が割り当てられており、昇順でソートする場合を考える。
ここでは、シンプルで直感的な「挿入ソート」を取り上げる。

リスト内の各要素を一度に1つずつ確認し、それを新しいリストに昇順もしくは降順になるように挿入していく（挿入セクション）と、ソートが完成するまで繰り返し挿入を行うソートセクションの二つのセクションで、壮途を実現する。
・挿入タスク：
１）ファイルが入っていない新しいファイリングキャビネットがあると想定する。そこに新しいファイルを挿入することを考える。この場合、単純に、そのしいファイリングキャビネットにその新しファイルをいれればよい。
２）次の新しファイルをこのファイリングキャビネットに挿入する場合は、ファイリングキャビネットに入っているファイルの番号と、次の新しいファイルの番号を確認し、後者が大きければもとのファイルの後ろに挿入する。小さければもとのファイルの前に挿入する。こうすると、2つのファイルは昇順に並ぶことになる。
３）次の新しファイルをこのファイリングキャビネットに挿入する場合は、ファイリングキャビネットに入っているファイルの番号と、次の新しいファイルの番号を確認し、後者が大きければもとのファイルの後ろに挿入する。小さければもとのファイルの前に挿入する。こうすると、2つのファイルは昇順に並ぶことになる。
４）次の新しファイルをこのファイリングキャビネットに挿入する場合は、ファイリングキャビネットに入っている一番後ろのファイルの番号と、次の新しいファイルの番号を確認し、後者が大きければもとのファイルの後ろに挿入する。小さければもとのファイルの前のファイルがあればそのの番号と比較し、次の新しいファイルの番号の方が大きければ、その後ろに挿入する。もとのファイルの前のファイルがなければ一番前に挿入してこのタスクを終了する。もとのファイルの前のファイルがある場合は、これらを繰り返す。そうすると、挿入されたファイルを含めて、キャビネット内に昇順に並ぶことになる。

・マージ：順次、ソートしたいファイルを、上記の挿入ソートの手順で順次行い、ソートしたいファイルがなくなればソートは終了する。

Pythonによるプログラム例：

#挿入ソートプログラム
def insert_cabinet(cabinet,to_insert): #挿入タスク
check_location = len(cabinet) – 1
insert_location = 0
while(check_location >= 0):
if to_insert > cabinet[check_location]:
insert_location = check_location + 1
check_location = – 1
check_location = check_location – 1
cabinet.insert(insert_location, to_insert)
return(cabinet)

def insertion_sort(cabinet): #マージタスク
newcabinet = []
while len(cabinet) > 0:
to_insert = cabinet.pop(0)
newcabinet = insert_cabinet(newcabinet, to_insert)
return(newcabinet)

cabinet = list(map(int, input(“ソートしたい数字列を半角でスペースで区切って記載してください　”).split()))
# 4 1 3 2 6 3 18 2 9 7 3 1 2 5 -9　← 入力例

sortedcabinet = insertion_sort(cabinet) #挿入ソート実施
print(“ソートした数字列　”,sortedcabinet) #結果出力

 

参考とした書籍
署名：アルゴリズムをめぐる冒険–勇敢な初学者のためのPythonアドベンチャー
著者：Bradford Tuckfield
訳者：竹川文則、川上悦子、高柳愼一
発行所：共立出版(株)

以上