トップ過去問一覧応用情報技術者 平成20年・秋 > 問11
問11

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

○正解
×不正解

n

n2

log n

n log n

解説

単純挿入法の比較回数のオーダは通常O(n2)ですが、整列済みのデータ列に対してはO(n)になります。

 

その理由は、挿入法のアルゴリズムにあります。挿入法のアルゴリズムでは、整列済みのデータ列に対して未整列データの挿入を繰り返します。そのデータ挿入の際、挿入位置を決めるために整列済みのデータ列の端から順に比較をします。データ列が整列済みの場合は、1回の比較で挿入位置が決まるため、全体の比較回数が少なくなります。

 

以下で具体例を挙げて説明します。[]で囲まれた部分が整列済みとします。最初は一番左のデータだけが整列済みの状態で始まります。

 

(1) [8] 12 23 45 48

12を挿入位置を決めます。8<12ですので8の後ろに挿入します。

 

(2) [8 12] 23 45 48

23を挿入位置を決めます。12<23ですので12の後ろに挿入します。

 

(3) [8 12 23] 45 48

45を挿入位置を決めます。23<45ですので23の後ろに挿入します。

 

(4) [8 12 23 45] 48

48を挿入位置を決めます。45<48ですので48の後ろに挿入します。

 

(5) [8 12 23 45 48]

 

すべてのステップにおいて、1回の比較でデータ挿入位置を決定できています。データが整列済みでない場合は、こうはいきません。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。