【Python】挿入ソートを実装してみた

挿入ソートを実装してみました。

挿入ソートは、バブルソート、選択ソートと並んでシンプルなソートアルゴリズムです。

アルゴリズム

アルゴリズムはシンプルで左から順番に値を取り出し、大小関係が保たれるように挿入していくだけです。

1回目から繰り返し処理の中身をみていきます。

1. 何もしない
2. 28を15と34の間に挿入する。
3. 11を先頭に挿入する。
4. 何もしない
5. 21を15と28の間に挿入する。
6. 何もしない

1 [15, 34, 28, 11, 36, 21, 42]
2 [15, 34, 28, 11, 36, 21, 42] 
3 [15, 28, 34, 11, 36, 21, 42]
4 [11, 15, 28, 34, 36, 21, 42]
5 [11, 15, 28, 34, 36, 21, 42]
6 [11, 15, 21, 28, 34, 36, 42]
[11, 15, 21, 28, 34, 36, 42]

コード

def InsertionSort(num_list):
  n = len(num_list)
  for i in range(1,n):    
    j = i
    print(i,num_list)
    while j > 0:
      if num_list[j] < num_list[j-1]:
        num_list[j],num_list[j-1] = num_list[j-1],num_list[j]
      j -= 1
  return num_list

終わり。