【挿入ソート法とは】リストの昇順・降順ソートの原理と計算量

(単純・基本)挿入ソート法とは?リストを昇順・降順ソートする原理・アルゴリズムについて解説します。

【挿入ソート法とは】リストを昇順・降順ソート

(単純・基本)挿入ソート法とは、あらかじめソートが終わっているリストに、データを挿入していく整列アルゴリズムです。

順序 操作
最悪計算時間がO(n^2)と計算時間が大きい(低速)。
整列済みのリストに新しい要素を追加するときは、効率が良い(完全にランダムな並び順だと効率が悪いので適していない)。

【計算例】昇順ソート

理解を深めるために、あらかじめ先頭3つの要素がソート済みである5つの要素をもつリスト[4, 5, 7, 6, 2]の昇順ソートを挿入ソート法で行ってみます。

リストの状態 操作
[4, 5, 7, 6, 2] 4番目の要素(6)とソート済み要素群のうち、一番後ろにある3番目の要素(7)を比較します。4番目の要素(6)の方が小さいので、次に2番目の要素(5)と比較します。
[4, 5,6, 7, 2] 4番目の要素(6)の方が大きので、2番目の要素の後ろに4番目の要素(6)を挿入します(これで1~4番目の要素はソート済となる)。
[2, 4, 5, 6, 7 ] 5番目の要素(2)と4番目の要素を比較します。5番目の要素(2)の方が小さいので、次に3番目、2番目、1番目と順に比較します。1番目まできても5番目の要素(2)の方が小さいので、2は先頭にもっていきます。

【計算コスト】挿入ソートの計算時間

挿入ソート法の処理は、N個の要素を持つリストに対してi = 2, 3, …, Nと同様な操作を繰り返すので、最効率な探索回数は「n + (n-1) + … + 3 + 2 = n(n+1)/2 – 1」となります。
また、要素の比較と入れ替え回数は 「(n-1) + (n-2) + … + 3 + 2 = n(n-1)/2」となります。
よって、挿入ソートの計算量は O(n^2) となります。

【プログラミング】挿入ソートの実装

プログラミング言語で挿入ソートを実装する方法については、言語別に下記事で紹介しています。

メディアを追加

詳細記事
1 【Python】挿入ソート法を実装
おすすめ記事
1 【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
2 【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
コンピュータ
技術雑記

コメント

タイトルとURLをコピーしました