平成20年秋期  問11

こめかみさん  
(No.1)
解説文が問題そぐわないものになっていると思います。

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


本問は単純挿入整列法を用いて、「昇順に整列済みの大きさnのデータ列を,改めて昇順に整列する処理を行う」ことが主旨のため、各要素を改めて挿入する際に末尾の要素との比較のみで挿入位置が確定することに着目すべきです。

例:
(1, 3, 5, 7)の整列済みデータ列を再整列する際、次の様なステップとなる
ステップ1: 1を新たなデータ列に加える
ステップ2: 3と末尾の要素1を比較し、3を1の後ろに加える
ステップ3: 5を末尾の要素3と比較し、5を3の後ろに加える
ステップ4: 7を末尾の要素5と比較し、7を5の後ろに加える

整列済みのデータの各要素を順番に挿入するため、挿入しようとしている要素は常に新たなデータ列の末尾の要素よりも大きくなります。
このため、各要素の挿入位置は1回の比較で確定し、これを要素の数だけ繰り返すため、オーダーはO(n)となります。
2024.09.22 11:53
jjon-comさん 
AP プラチナマイスター
(No.2)
ソフトウェア開発 平成20年 秋期 午前 問11
https://www.ap-siken.com/kakomon/20_aki/q11.html

No.1の指摘は全面的にそのとおりなのですけれど,

> ステップ1: 1を *新たなデータ列に加える*

という表現が気になりました。
元の配列とは別に整列済み配列格納用の新たな領域を用意する,という表現のように読めたということです。具体的イメージはこんな感じです。
初期状態:
整列前|1|3|5|7|
整列後

ステップ1:
整列前|*1|3|5|7|
整列後|1|

ステップ2:
整列前|1|*3|5|7|
整列後|1|3|

ステップ3:
整列前|1|3|*5|7|
整列後|1|3|5|

ステップ4:
整列前|1|3|5|*7|
整列後|1|3|5|7|

それに対して。
単純挿入整列法(挿入ソート)は,整列済み配列格納用の新たな領域を用意せず,元の配列を書き換えることで実現できます。配列の前方が整列済,後方が未整列。具体的イメージはこんな感じです。

初期状態:
|1|3|5|7|

ステップ1: T[1]は要素が1つだけなので整列済とする。
[1]|3|5|7|

ステップ2: 次の挿入要素としてT[2]をXに取り出し。XとT[1]の大小比較で挿入位置を探し,挿入。整列済み長は2となる。
[1|3]|5|7|

ステップ3: 次の挿入要素としてT[3]をXに取り出し。XとT[2],XとT[1]の大小比較で挿入位置を探し,挿入。整列済み長は3となる。(この問題ではXとT[2]の比較ですぐに挿入位置が決定)
[1|3|5]|7|

ステップ4: 次の挿入要素としてT[4]をXに取り出し。XとT[3],XとT[2],XとT[1]の大小比較で挿入位置を探し,挿入。整列済み長は4となる。(この問題ではXとT[3]の比較ですぐに挿入位置が決定)
[1|3|5|7]
2024.09.22 15:46
こめかみさん  
(No.3)
単純挿入整列法について充分に理解しないまま投稿してしまいました。元の領域を左から固めていくイメージですね。
大変勉強になりました。ご指摘いただきありがとうございます。(投稿に返信いただけたことが嬉しいです!)
2024.09.22 16:52
boyonboyonさん 
AP シルバーマイスター
(No.4)
横から失礼します。
この問題の解釈ですが、
大きさNのデータ列(N>n)を挿入ソートで整列する。
現在、n番目まで整列できた。
ここで、次の要素を挿入してn+1個の整列済みデータ列を作る場合の比較回数(上限)を問うていると思うのですが。
どうでしょうか。
2024.09.22 22:49
jjon-comさん 
AP プラチナマイスター
(No.5)
[昇順に整列済みの大きさnのデータ列] を,[改めて] 昇順に整列する処理
ですから,前者の[]と後者の[]は大きさnの同じ配列領域を指すものと読解できます。n+1番目の要素の存在はこの文からは読み取れません。

ちなみに。

> 現在、n番目まで整列できた。
の具体例を次のようだとしたとき,
|1|3|5|7|

> 次の要素を挿入して
の「次の要素*」はどんな値をイメージしているのでしょうか。

|1|3|5|7|2*|
のように整列されていない新たな要素の追加をイメージしているのなら,
[改めて] 昇順に整列する
という表現に合いません。

|1|3|5|7|9*|
のように整列された新たな要素の追加をイメージしているのなら,この計算量(オーダ)は N ではなく 1 です。
2024.09.23 10:09

返信投稿用フォーム

※SQL文は全角文字で記載してください。
※宣伝や迷惑行為を防止するため、当サイト、姉妹サイト、IPAサイト以外のURLを含む記事の投稿はできません。

投稿記事削除用フォーム

投稿番号:
パスワード:

その他のスレッド


Pagetop