(1) 挿入ソート
挿入ソートとは
挿入ソートは、データを抜き出して、順番に並ぶ位置に挿入していく方法です。
手順
- 配列の先頭を整列済みとします。
- 未整列部分の先頭を変数tmpに入れます。
- tmpの値を整列済みのどこに挿入するかを、整列済みの値を後から調べていきます。
- 整列済みのうちtmpより大きい要素を順に、右に１つずつずらします。
- (4)の処理が終わったら、そこにtmpを挿入します。
- すべての要素が整列済みになるまで、(2)〜(5)を繰り返します。
デモンストレーション
プログラム
Colaboratoryのノートブックに書き写しながら、理解しましょう。
for文を使った挿入ソートのプログラム
整列済みのうちtmpよりも大きい要素を順に、右に１つずつ移動する操作をfor文で表すと次のようになります。
arr = [6, 3, 2, 0, 7, 1, 4, 5] # 元のリスト
print(arr) # ソート前を出力
n = len(arr)
print("------------------------")
for i in range(1, n): # 未整列部分から、順番に１つずつ値を取り出していく
tmp = arr[i] # 挿入する値を変数tmpに入れる
ins = 0 # 挿入する位置の変数(初期値は暫定的に0)
for j in range(i - 1, -1, -1): # 整列済みのどこに挿入すればいいかを、後から前に向かって順番に比較していく
if arr[j] > tmp: # もし挿入する値が小さければ、
arr[j + 1] = arr[j] # 調べた値を１つずつ後にずらす
else: # そうでなければ、
ins = j + 1 # 挿入する位置をj+1に確定する
break # ずらす処理を止める
arr[ins] = tmp # ずらす処理が終わった位置に挿入する値を入れる
print(arr) # 途中経過を出力
print("------------------------")
print(arr) # ソート後
[6, 3, 2, 0, 7, 1, 4, 5]
------------------------
[3, 6, 2, 0, 7, 1, 4, 5]
[2, 3, 6, 0, 7, 1, 4, 5]
[0, 2, 3, 6, 7, 1, 4, 5]
[0, 2, 3, 6, 7, 1, 4, 5]
[0, 1, 2, 3, 6, 7, 4, 5]
[0, 1, 2, 3, 4, 6, 7, 5]
[0, 1, 2, 3, 4, 5, 6, 7]
------------------------
[0, 1, 2, 3, 4, 5, 6, 7]
for j in range(i - 1, -1, -1)について、ステップが負数になるときの指定のしかたは、2-4. 繰り返し処理（for文）① 減っていくforループを参照してください。
while文を使った挿入ソートのプログラム
整列済みのうちtmpよりも大きい要素を順に、右に１つずつ移動する操作をwhile文で表すと次のようになります。
arr = [6, 3, 2, 0, 7, 1, 4, 5] # 元のリスト
print(arr) # ソート前を出力
n = len(arr)
print("------------------------")
for i in range(1, n): # 未整列部分から、順番に１つずつ値を取り出していく
tmp = arr[i] # 挿入する値を変数tmpに入れる
j = i - 1 # jはiのひとつ前から先頭に向かって1ずつ減らしながら繰り返す
while j >= 0 and arr[j] > tmp: # jの値が正かつj番目の要素がtmpよりも大きいあいだ繰り返す
arr[j + 1] = arr[j] # j番目の要素をひとつ右に移動する
j = j - 1 # jの値を1減らす（ひとつ前の要素を次の対象とする）
arr[j + 1] = tmp # whileループが終わったら（tmpよりも大きい要素は１つずつ右に移動している）、j+1番目にtmpを代入する
print(arr)
print("------------------------")
print(arr) # ソート後
[6, 3, 2, 0, 7, 1, 4, 5]
------------------------
[3, 6, 2, 0, 7, 1, 4, 5]
[2, 3, 6, 0, 7, 1, 4, 5]
[0, 2, 3, 6, 7, 1, 4, 5]
[0, 2, 3, 6, 7, 1, 4, 5]
[0, 1, 2, 3, 6, 7, 4, 5]
[0, 1, 2, 3, 4, 6, 7, 5]
[0, 1, 2, 3, 4, 5, 6, 7]
------------------------
[0, 1, 2, 3, 4, 5, 6, 7]
このアルゴリズムの特徴
最大比較回数・最大交換回数
最大交換回数は、すべての比較において交換する場合なので、最大交換回数＝最大比較回数となります。
0番目の要素は比較・交換をしなくても整列済みとします。
1番目以降の要素は、比較回数が最も多くなるのは、要素を左端まで交換していくときです。つまり、1番目の要素は最大1回，2番目の要素は最大2回，・・・，\(n-1\) 番目の要素は最大 \(n-1\) 回となるので、
\[ 最大比較回数・最大交換回数 = 1 + 2 + \cdots + (n-1) = \frac{1}{2}n(n-1) \]となります。
最小比較回数・最小交換回数
最も比較回数が少ない場合は、すでに整列済みの配列の場合です。
0番目の要素は比較・交換しなくても整列済みとします。
1番目以降の要素は、比較回数が最も少なくなるのは、整列済みの右端と比較するときなので、1番目の要素は最小1回，2番目の要素は最小1回，・・・，\(n\) 番目の要素は最小１回となるので、
\[ 最小比較回数 = n-1 \]となります。
また、このとき交換は起こらないので、最小交換回数は0(ゼロ)となります。
平均比較回数・平均交換回数
1番目以降の要素について、平均比較回数と平均交換回数は、挿入位置が整列済みの中央になるときと考えられます。
つまり、\(i\) 番目の要素を挿入する場合、整列済みの要素は \(i\) 個あるので、平均比較回数と平均交換回数は、\(i/2\) 回となります。つまり、1番目の要素は\(1/2\) 回，2番目の要素は\(2/2\) 回，・・・，\(n\) 番目の要素は\((n-1)/2\) 回となるので、
\[ 平均比較回数・平均交換回数 = \frac{1}{2} + \frac{2}{2} + \cdots + \frac{n-1}{2} = \frac{1}{4}n(n-1) \]となります。
このアルゴリズムの特徴
バブルソートは、隣り合う２つの値を比較していきますが、挿入ソートでは離れた位置の値を比較して適切な位置に挿入を行っていくので、整列されている部分が多いほど交換回数が少なくなり、他の複雑なアルゴリズムよりも高速に並び替えができます。例えば、要素が頻繁に追加され、その都度並び替えを行うような環境では、追加された要素をすぐに正しい位置に挿入できます。
平均交換回数は \(n^2\) に比例して大きくなりますが、ある程度に分割することによって効率よくソートすることができます。このように分割した配列に挿入ソートをする方法は、シェルソートやマージソートという別のアルゴリズムに応用されています。