クイックソートで並べ替え

質問

友人から情報処理の質問を受けました。ですが、私では良く分からなかったので質問します。

2,4,8,1,6,5,2,7,3,7の整数をクイックソートで並べ替えよ。
また、比較回数を示せ（軸要素は先頭の2要素のうち大きいほうとせよ）。

よろしくお願いします。

回答No.5

buriburi3

この場所では「課題の丸投げ」は禁止されているので解答に自信が無いなら、その解答を示して正否を問うのがルールです。
その友人の解答をここに提示してください。

回答No.4

yama5140

No.3 です。

＞私含めて本人もソースだとかプログラムが一切分かりません。
＞手順自体は、検索したようで理解しているらしいのですが、回答に自信がないらしく正解を知りたいとのことです。

　「Ｃ＆Ｃ＋＋でプログラムし、結果（比較回数）を回答しろ」、ということですね。
　でしたらこのコミュニティーには相応しくないのでは・・。

☆アンケート形式にしちゃえば、ぎりぎりセーフかも。

　昇順にソートしたとき、比較○回に１票。
　降順にソートしたとき、比較◇回に１票・・とか。

＞軸要素は先頭の２要素のうち大きいほうとせよ

　って、対象が、2,4,8,1,6,5,2,7,3,7 となっていることから自明ですよね。
　（「先頭」は１つしかないっつうツッコミは無しとして）

☆「軸要素は４とせよ」という記述ではないことから、やはり（様々な条件に対応可能な）プログラムを作る、のが「そもそも」ではないでしょうか。
+++++++++++++++++++++++++++++++++++++
アンケート形式として、年寄りは、

　昇順にソートしたとき、比較 15 回に１票。
　降順にソートしたとき、比較 16 回に１票。

注：全然自信がありません（まっアンケートだから、「良」として下さい）。

「バブル」なら 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 で固定かなぁ・・？。

お礼

返信ありがとうございます。
本人は回答よりも筋道を知りたかったようですが、自己解決したらしいのでこれにて〆ます。
何度もありがとうございました。

回答No.3

yama5140

＞2,4,8,1,6,5,2,7,3,7の整数をクイックソートで並べ替えよ。

　http://okwave.jp/qa4557292.html

　この質問文中のソースに、「比較回数」処理を追加し、試されたら如何でしょう。

補足

私含めて本人もソースだとかプログラムが一切分かりません。
手順自体は、検索したようで理解しているらしいのですが、回答に自信がないらしく正解を知りたいとのことです。

もし拝見されたら分かる限りで教えてくださるとありがたいです。
よろしくお願いします。

回答No.2

jacta

qsortにせよ、std::sortにせよ、アルゴリズムとしてクイックソートが使われていることは保証されていません。
また、仮にクイックソートで実装されていたとしても、

> 軸要素は先頭の2要素のうち大きいほうとせよ

という要件を満たすことができません。

#1の回答のとおり、検索すればすぐに結果が得られますので、その旨お伝えください。

補足

先の補足とダブりますが、手順自体は検索したようで理解しているらしいのです。ただ、回答に自信がないらしく正解を知りたいとのことです。

もし拝見されたら分かる限りで教えてくださるとありがたいです。
よろしくお願いします。

回答No.1

buriburi3

コールバックを定義してqsort()呼び出すだけです。
参考　http://wiki.livedoor.jp/cafeboy1/d/C/C%2B%2B%20qsort(QuickSort)
C++ならSTLが使えます。
(コンパイラによってはSTLがまともに使えない事もありますが)

課題か何かでクイックソートルーチン自体を作らなければならないのでたら「ググれカス」とお伝えください。

補足

伝えたところ、C++って何？という返答が返ってきました。
本人曰く、上記の問題はプログラムなどを使うのではなく、あくまで手動での筆記問題とのことです。
手順自体は、検索したようで理解しているらしいのですが、回答に自身がないらしく正解を知りたいとのことです。

もし拝見されたら分かる限りで教えてくださるとありがたいです。
よろしくお願いします。