Photo by
h_fujieda
#8 挿入ソート
今回は挿入ソートについて説明します。
整列してある配列に追加要素を適切な場所に挿入すること。
基本的なソートアルゴリズムの一つです。
クイックソートなど良く使われるソートアルゴリズムと比較して遅いですが、シンプルなアルゴリズムなため実装しやすいメリットがあります。
コード
def insert_sort(lists):
n=len(lists)
print('元データ:',lists)
cnt=0
for i in range(1,n):
tmp=lists[i]
j=i
while j>0 and lists[j-1]>tmp:
lists[j] = lists[j-1]
j=j-1
cnt+=1
lists[j]=tmp
print(lists,i)
print('ソート後:',lists)
print('入れ替え回数:',cnt)
def gen_val(n):
return [r.randint(0,1000) for i in range(0,n)]
if __name__ == "__main__":
a=gen_val(10)
start=t.time()
insert_sort(a)
print(t.time()-start)結果
左から一つずつデータを見ていき、対象のデータを適切な順番に並べ変えています。
例えば2、3回目のソートの時は82のデータは4番目から最初の位置に並べ替えられてます。
このようにデータを左から見ていき一つずつデータを適切な位置に置いていきます。
元データ: [557, 338, 565, 82, 467, 784, 733, 589, 919, 10]
[338, 557, 565, 82, 467, 784, 733, 589, 919, 10] 1
[338, 557, 565, 82, 467, 784, 733, 589, 919, 10] 2
[82, 338, 557, 565, 467, 784, 733, 589, 919, 10] 3
[82, 338, 467, 557, 565, 784, 733, 589, 919, 10] 4
[82, 338, 467, 557, 565, 784, 733, 589, 919, 10] 5
[82, 338, 467, 557, 565, 733, 784, 589, 919, 10] 6
[82, 338, 467, 557, 565, 589, 733, 784, 919, 10] 7
[82, 338, 467, 557, 565, 589, 733, 784, 919, 10] 8
[10, 82, 338, 467, 557, 565, 589, 733, 784, 919] 9
ソート後: [10, 82, 338, 467, 557, 565, 589, 733, 784, 919]
入れ替え回数: 18
処理時間:0.008878946304321289参考書籍
いいなと思ったら応援しよう！
