アルゴリズムの問題なのですが、マージソートとクイックソートについて教え
アルゴリズムの問題なのですが、マージソートとクイックソートについて教えてください。
数列の(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を選んだ)
これではいけないのでしょうか。
長くなりましたが、よろしくお願いします。
お礼
ありがとうございます