応用情報技術者 試験情報＆徹底解説

解説に要素数4の配列に2を挿入する場合を考えるとありますが、この問題は要素数nの昇順配列をもう一度昇順にソートする場合のオーダーを求めるのではないのでしょうか？
この場合、解説の例(1,3,5,7)の配列を用いると、
・1を配列末尾の0（空配列）と比較し挿入する（比較計1回）
・3を配列末尾の1と比較し挿入する（比較計2回）
・5を配列末尾の3と比較し挿入する（比較計3回）
・7を配列末尾の3と比較し挿入する（比較計4回）
となり、オーダーはnということでしょうか？

また、末尾ではなく先頭から比較する場合はオーダーはどうなりますか？

オーダーはアルゴリズムの計算量を表すので、"最悪何回かかるかな"という目安値です。

例にある要素数4の配列なら、先頭からでも末尾からでも、最短1回/最悪4回の比較になります。

要素数nの配列に、要素n+1を追加する場合は、最短で1回/最悪n回の比較になります。

先頭からの比較回数は0の場合1回のみですがO(n)に変わりありません。

えーいさん

ご回答ありがとうございます。
もう少し質問させてください。
「要素数nの配列に、要素n+1を追加する場合は、最短で1回/最悪n回の比較になります。」ということに関しては理解しているつもりです。
ただ、本問は「要素数nの配列にさらに1つ要素を追加する」のではなく、「昇順にソートされた要素数nの配列を、先頭からもう一度昇順にソートする」という内容ではないでしょうか？
もし、後者ではなく前者を問われているのだとすると、問題文のどの部分からそれを読み取ることができるのでしょうか？

末尾ではなく先頭から比較する場合、
・1を配列先頭の0（空配列）と比較し挿入する（比較計1回）
・3を配列先頭の1と比較し、1の後ろに挿入する（比較計2回）
・5を配列先頭の1と比較し、次に3と比較し、3の後ろに挿入する（比較計4回）
・7を配列先頭の1と比較し、次に3と比較し、最後に5と比較し、5の後ろに挿入する（比較計7回）
となるのではないかと考えています。

改めて問題を確認します。

昇順に整列済みの大きさnのデータ列を，改めて昇順に整列する処理を行う場合の比較回数

ここでは整列済みのデータ列の末尾から挿入ソートで処理するというアルゴリズムなので、

1番目の要素を取り出して、n番目から2番目までn-1回比較することになります。これはすでに昇順に整列済みだからです。
定数を除去してオーダはO(n)になります。

先頭からの揃え直しは考える必要がありませんが
、仮に先頭から整列済みのデータ列に挿入ソートを考える場合も同様に、
n番目の要素を取り出して、1番目からn-1番目までn-1回比較することになるので結果は変わりません。

ちなみに挿入ソートについてですが、
今回は整列済みの基本挿入ソートなのでO(n)
これが非整列の配列の場合はO(n^2)になります。
これは比較回数がn(n-1)/2回になるからです。

その他のソートについても考え方とオーダを把握しておくとよいですよ。

末尾から比較する場合の比較回数：n-1
先頭から比較する場合の比較回数：1/2×n×(n-1)

n=4の場合、前者は3回で後者は6回
マウスさんは、最初の挿入時にも1回比較するとみなしているので
1回差異が生じています。

なのでオーダーは、
末尾から比較する場合：O(n)
先頭から比較する場合：O(n^2)
（だと思うのですが）

えーいさん

ご回答ありがとうございます。
何度も申し訳ありませんが、まだ疑問が残りますので質問させてください。
「要素数nの配列に要素を1つ追加する場合のオーダーはn」というのは、おそらく共通の認識だと思います。
回答にある、「1番目の要素を取り出して、n番目から2番目までn-1回比較することになります。」というのは、配列(1,3,5,7)を例にとると、配列(1,3,5,7)に先頭要素の1を挿入する場合のことをおっしゃっているのでしょうか？
その場合ですと確かに先頭要素の1を挿入するオーダーはnですが、本問は要素数nの配列を挿入すると思うので、オーダーはn^2になりませんか？

Howitzerさん

ご回答ありがとうございます。
私の言いたかったことはそういうことです。分かりやすくまとめていただきありがとうございます。
最初の比較を行うかは私も迷っていたところですが、行わないのが正しいのですね。
先頭から比較を行う場合、n=4のとき6回、n=100のとき4950回と、n^2の半分以下になるので、オーダーはどのように表現するのだろうという疑問でしたが、n^2で良いのですね。

この投稿は投稿者により削除されました。(2021.12.23 13:41)

申し訳ありません、間違えました。

先頭からの挿入ソートにした場合、整列済みが最大試行回数になるのでn(n-1)/2→O(n^2)です。

失礼しました。

疑問を解消できて良かったです！
皆さんありがとうございました！