アルゴリズムによる整列方法について

質問

以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。
先生も答えてくれません。
解答お待ちしております。

１．以下の文章の空欄を埋めよ．但し，((14)),((15)) については，選択肢から最も適切なものを選び，記号で答えよ．加えて，解答の過程を詳しく述べよ。

高速な整列として以下のアルゴリズムによる方法を考える．以下では，整数データを昇順に配列するも
のとする．

前段階として，データを半々に二つのグループ I と II に分割し，それぞれを独立に整列する．
while (両グループに要素が残っている)
do
　　 if (グループ I の最小要素 < グループ II の最小要素)
　　 then 　グループ I の最小要素を出力場所に移し，グループ I からは削除する
　　 else 　グループ II の最小要素を出力場所に移し，グループ II からは削除する
　　 endif
done
while (グループ I に要素が残っている) do
　グループ I の要素を出力場所に移し，グループ I からは削除する
done
while (グループ II に要素が残っている) do
　グループ II の要素を出力場所に移し，グループ II からは削除する
done

この整列に要する計算量 T(n) を求める．但し，n は整列するデータの量である．前段階の整列では，半分のデータ量の整列を 2 回行うので ((1)) だけの計算を要する．次に，3 個の while 反復のいずれについても，
「反復を 1 回行うごとに要素が一つだけ出力場所に移動する」
ことから，3 個を合計すると反復の中身は正確に ((2)) 回実行されることが分かる．1 回の実行に a
だけの時間がかかるものとすれば，全体で ((3)) となる．従って次の関係式が成り立つ．
T(n) = ((4))
簡単のため，n = 2^p であるとすると，
T(n) = ((5))×T(2^((6)) ) + ((7))
　　 = ((8)) × T(2^((9)) ) + 2 × ((7))
　　　・
　　　・
　　　・
　　　= ((10)) × T(2^0) + ((11))
T(2^0) = ((12)) なので，T(n) を a と n のみを用いて表すと，
T(n) = ((13))
であり，これは， ((14)) に比例し，計算量のオーダーは ((15)) といえる．
((14)),((15)) の選択肢
a. n
b. n^2
c. 2^n
d. n log n
e. log n
f. いわゆる「指数オーダー」であり，アルゴリズムとして全く実用に耐えない
g. いわゆる「バカソート」と同じであり，n がごく小さい場合を除いて実用には適さない
h. 経験上最速とされるソート法には及ばないが，それほど大きくない n に対しては実用に耐える
i. 経験上最速とされるソート法と同じであり，十分大きい n に対しても実用に耐える

回答No.4

kmee

このアルゴリズムはやってないかもしれませんが、他のアルゴリズムや、その「計算量」の考え方はやってますよね?
何の前振りも無しに、こんな問題を出すとは思えません。
他のアルゴリズムだはどんなことやっていたか、復習してみましょう。

n個の整列にかかる時間がT(n)なら、n/2個の整列にかかる時間はT(n/2)です。
(4)は、具体的な計算をするのではなく、T(n/2)や他の値を使って、T(n)との関係だけを求めておきます。
実際の値の計算は、とりあえず、置いておきます。

※ (5)以降が、その具体的な計算をしていくところです。

コンピュータになったつもりで、御自身で具体的にやってみるのもよいでしょう。

トランプを用意します。
全部使ってもよいのですが、わかりにくいので、スペードだけを使います(ハートでもいいですけど)

場に
J
Q
K
と置きます。

1～10のカードを裏返して混ぜ、5枚ずつに分割します。
片方を、小さいカードが上になるように順番に並べて、Jの横に置きます。
もう片方は同様にしてQの横に置きます。

例えば、こういう状態になったとします
J; 4
Q: 1
K;

これが「前段階として，データを半々に二つのグループ I と II に分割し，それぞれを独立に整列する．」の部分です。
JがグループI,QがグループIIです。

ここから、アルゴリズムに従って処理します。

まず最初に。
JもQもあるので、「while (両グループに要素が残っている)」の部分です。
各グループの最小値は、一番上です。 4 と 1 を比べれば 1が小さいです。
従って、 1 を QからKへ移動します。
J; 4
Q: ↓
K; 1
ここまでが「1回」で、時間は a だけかかります。

ここで、 JとQは整列してあるので、最小値を探すには、一番上を見ればいいことになります。
人間だと、5枚くらいなら、全部表にして並べて、一番小さいカードを探しても大して苦ではありません。
ですが、コンピュータにはそんなことはできません。いちいち全部のカードを調べて探さなければなりません。
それを、「整列しておいて、先頭だけを見る」とすることで、コンピュータでも楽に最小値を探すことができます。

これを繰り返していくと、
J; 無し
Q: 9
K; 1 2 3 4 5 6 7 8
のような状態になります。ここからは
「while (グループ I に要素が残っている) do」
「while (グループ II に要素が残っている) do」
に従って、残っているカードを1枚ずつKへ移動します

全部終わると
J; 無し
Q: 無し
K; 1 2 3 4 5 6 7 8 9 10
とKの整列ができあがります。

かかる時間は
T(10)=「Jに並べる時間」+「Qに並べる時間」+ 「Kへ移動させた回数」× a
になるのがわかると思います。
JとQを並べるのに、このアルゴリズムを使えば、「5枚並び換える時間」ですから
T(10)=T(5)+T(5) + 「Kへ移動させた回数」× a
になります。
「Kへ移動させた回数」は....もうわかりますよね?

実はアルゴリズムは有名なもので、名前も付いています。
それで検索すれば解説も「答え」も見つかってしまうのですが....とりあえずは黙っておきます。

あと「バカソート」って何のことだろう?
計算量の話ならバブルソートかな、とも思いますが、「バカ」って意味では、ボゴソート、ボゾソートの方が「バカ」ですし。

回答No.3

中村 拓男（@tknakamuri）

学術的には名前があるのかもしれませんが、
ナチュラルマージソートをちょっと非効率にしたようなソートですね。

質問にはありませんが、分割は1個までやってしまうのでしょうね。
＃実際にはデータを一度スイープすればどこまで分割が必要か判断できるので
＃1個まで分解したりはしないです。

T(2^p)
=2 X T(2^(p-1)) + a x 2^(p)
=2 x (2 x T(2^(p-2)) + a x 2^(p-1)) + a x 2^(p) = 4 x T(2^(p-2)) + 2 x a x 2^(p)
= 2^p x T(1) + pa x 2^p = nT(1) + pan = nT(1) + logn・an

なので a に比例して nlogn のオーダーなのでしょう。

オンラインで書いたので、間違っていたらすいません。

回答No.2

kmee

まず、あなたがどこまで埋めることができたのか、教えてくれませんか?

ほとんどは、 T(x),n,p,a を使った式です。
2^p=n より、 p = log n ということも利用しましょう。
データ量n個の時間がT(n)なら、「半分のデータ量」はn/2で、その時間はT(n/2)です。

14,15の選択肢ですが、 14には a～e,15にはf～iが入るのはわかるかと思います。
14が決まれば15が決まります。また、相手の無い選択肢があります。
それはわかりますか?

※ hとiは解釈にちょっと困る

お礼

#1さんにもお答えしたとおり、全く分からないのです。最初から、何を言っているのかわかりません。
前段階の話からついていけません。

前段階で整列？が必要なのでしょうか？
何回？それはどのようにすれば求まりますか？（n-2）回とかでしょうか？

14と15の選択肢ですが、選択肢を見た感じ、片方（14）にlogなどが入り、もう片方（15）は言葉だろうな、という漢字のレベルでは認識していました。

回答No.1

Tacosan

「先生も答えてくれません」て, そりゃそうでしょう. そこで簡単に答えてしまうようでは, それこそ「授業外課題」になどなりもしないんだから.

で, なにをどのくらい考えた末の「わからない」ですか?

お礼

ありがとうございます。正直「全く分からない」です。
というのも、先生はアルゴリズムに関して全く授業で触れていません。買わされた教科書にも載っていません。なのにもかかわらず、この問題から試験を作成するとおっしゃっていました。「そういえば、こんな問題があるから、解いておいてね、テストに出すから」とのことです。なので、周りの友人たちもわからず、疲弊しきっています。