アルゴリズムの問題なのですが、マージソートとクイックソートについて教え

質問

アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。

数列の(21 99 38 22 15 6)をマージソートで並び変えて、クイックソートでも並び変えたいのです。

マージソートで並び変えた手順は
(21 99 38 22 15 6)
(下矢印)
(21 99 38)(22 15 6)
(下矢印)
(21 99)(38)(22 15)(6)
(下矢印)
(21)(99)(38)(22)(15)(6)
(下矢印)
(21 99)(38)(15 22)(6)
(下矢印)
(21 38 99)(6 15 22)
(下矢印)
(6 15 21 22 38 99)

となりました。
この時、分割回数と統合回数がともに5なのですが、どう見たら5回なのでしょうか。
分割回数は3で統合回数も3ではないのでしょうか？

クイックソートの方なのですが、

回答は
(21 99 38 22 15 6)
(下矢印)
(15 6)(21)(99 38 22)
(下矢印)
(6)(15)(21)(22 38)(99) (15と38にした場合)
(下矢印)
(6)(15)(21)(22)(38)(99)
となっていて、
最も効率のよいピボットを選択した場合分割回数は3となっています。

私がやってみたところ

(21 99 38 22 15 6)
(下矢印)
(15 6)(21)(99 38 22)
(下矢印)
(6)(15)(21)(22)(38)(99)　　(15と38を選んだ)
これではいけないのでしょうか。

長くなりましたが、よろしくお願いします。

回答No.2

nag0720 · ベストアンサー

マージソートについて
(21 99 38)(22 15 6)
↓
(21 99)(38)(22 15)(6)
この操作の分割回数は、右側の分割と左側の分割は別々の分割ですから２回と数えるべきです。

クイックソートは、正確には、
(21 99 38 22 15 6)
↓
(15 6)(21)(99 38 22)　 (ピボット＝21)
↓
(6)(15)(21)(22 38)(99)　 (ピボット＝15)
↓
(6)(15)(21)(22)(38)(99)　 (ピボット＝38)
のように書いたほうがいいでしょう。

＞(6)(15)(21)(22)(38)(99)　　(15と38を選んだ)
＞これではいけないのでしょうか。

単に、最後の２つを一緒にしただけです。
試験問題なら採点者がどう判断するかですから何とも言えません。
参考書に書いてあることなら、あなたが自分のほうが正しいと思っているならそれでいいのではないですか。

お礼

マージソートはわかりました！
私は一列変わったら１と数えていました。

クイックソートの
>>(6)(15)(21)(22 38)(99)　 (ピボット＝15)

ここの部分なのですが、ピボットが15を選んでいるにもかかわらず、(22 38)(99)と分けるのでしょうか。

回答No.1

Tacosan

まずマージソートの方から:
(21 99 38 22 15 6) とか
(21 99)(38)(22 15)(6) とかは何を意味するのですか? そして, あなたは何をどう数えて「分割回数」や「統合回数」を 3回としたのですか?
ついでクイックソートの方:
同じく
(15 6)(21)(99 38 22) などは何を意味するのですか? そして, 分割するアルゴリズムによって回数が変わる可能性があるのでアルゴリズムを示してください.