アルゴリズム (全82問中41問目)

No.41

整列済みの列の末尾から比較して,次の要素の挿入位置を決める単純挿入整列法について考える。昇順に整列済みの大きさnのデータ列を,改めて昇順に整列する処理を行う場合の比較回数のオーダは,どれか。

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

単純挿入整列法は挿入ソートとも呼ばれ、整列済みの要素と追加する要素を比較しながら適切な場所に挿入するアルゴリズムです。

例として「1,3,5,7」という昇順に整列された数列(n=4)に対して要素2を追加する場合を考えてみます。問題文の指示に従って比較は数列の末尾から行っていきます。
  1. 2と7を比較する。2のほうが小さいので数列の前の要素の比較に移る。
  2. 2と5を比較する。2のほうが小さいので数列の前の要素の比較に移る。
  3. 2と3を比較する。2のほうが小さいので数列の前の要素の比較に移る。
  4. 2と1を比較する。2のほうが大きいので要素2の挿入位置は1と3の間に決定する。
このように比較回数は最小で1回、最大でn回となることがわかります。オーダ記法では定数を除外した処理件数(n)による計算量の増加率や計算量の上限値を示すため、比較回数のオーダはO(n)になります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop