アルゴリズムクイックリファレンス 第2版

62

■

4

章 整列アルゴリズム

4.1.1

 挿入ソート

挿入ソート

（

Insertion Sort

）はヘルパー関数

insert

を繰り返し呼び出して

A[ 0, i ]

を正しく整列させる。最終的に、変数

i

が右端の要素に達したところで、

A

全体が

整列する。

挿入ソート

Insertion Sort

最良 平均 最悪

O(n) O(n

2

)

sort (A)

for pos = 1 to n-1 do

insert (A, pos, A[pos])

end

insert (A, pos, value)

i = pos - 1

while i >= 0 and A[i] > value do

❶

value

より大きな要素を右にシフト

A[i+1] = A[i]

i = i-1

A[i+1] = value

❷

value

を適切な位置に挿入

end

図4-3は、サイズ

n

＝

16

の小さな集まり

A

に、

挿入ソート

がどのように機能する

かを示している。各行は、

insert

の呼び出しごとに

A

の状態がどうなるかを示す。

A

の「上書き」整列は、添字を

pos

＝

1

から

n

−

1

まで増やしながら、要素

A[ pos]

を、整列済み領域

A[ 0, pos ]

内の正しい場所に置いていくことで行われる。次第に

成長する整列済み領域は、図4-3 では右端を太線で区切っている。灰色の要素は、

挿入要素のために場所を空けて、右側に移動する。全体として、

挿入ソート

は、（

1

要素を

1

コマずらす）移動を

60

回行う。