ソフトウェア開発技術者平成20年秋期 午前問11

問11

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

分類

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

正解

解説

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

例として「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-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop