並び替え

それぞれ異なる数が書いてある5枚のカードを７回の比較のみで並び替える方法は？と友達に聞かれたのですが、頭がこんがらがってわかりませんでした。友達も教えてくれないので気になって勉強に集中できません。
どなたか答えを教えてください<m(__)m>

No.7 回答者： Ishiwara 回答日時： 2008/07/18 01:18

＃５,６です。

クイックソートにこだわって回答して参りましたが、重大な欠点が見つかったので、撤回させていただきます。まことに申し訳ありません。

クイックソートは、実務上は極めて優秀な方法で、通常は他の追従を許さないのですが、理論的には弱みを抱えています。すなわち、わざと意地悪をして、クイックソートにとって不都合なデータを作ってやると、他の方法に負けてしまいます。試みに「４１５２３」から始めると、比較回数が８回になってしまいます。これでは回答になりません。

カードが２～４枚の場合は、（カード数×２）－３ですから、もし５枚で７回ということであれば、この式はそこまで成り立ちます。高々５枚であれば、根気よくあらゆる場合を想定すれば、解は簡単に求められると思います。例えば、トーナメント式の図を書きます。決勝までやって、比較回数は４です。２位の候補がどこにあるか、次いで３位の候補がどこにあるかを、順々に解決して行く方法が考えられます。ですが、一般に、数学好きな人は、そういう作業をやりたくないものです。

しかしポリアという人の『帰納と類比』という本に「そのような作業から法則を発見することがあるので、単純作業だからといって軽視してはいけない」という意味の教訓がありました。面白くない仕事ですが、そこから着手してはどうでしょうか。そのうちに、何か成果が得られるかもしれません。

No.6 回答者： Ishiwara 回答日時： 2008/07/17 13:42

＃５です。

クイックソートの原理を「再帰呼び出し」に触れないで説明しようとして、かえって論理的な破綻を起こしてしまいました。すみませんが、＃５を破棄してください。
次の手順を、ぜひトランプなどでお確かめください。

左から小さい順に並べることを最終目的とします。
(1)最初に左端札を「基準札」、右端札を「対象札」とします。この手順の目的は、基準札の位置を確定することです。
(2)基準札と対象札を比較し、
--大小関係が正しければ（つまり左のほうが小さければ）対象札の隣（基準札に近いほう）を新しい対象札として続行します。
--大小関係が逆ならば、基準札と対象札の位置を交換して続行します。
(3)こうしていつかは、基準札と対象札が隣接して、対象札の移動ができなくなります。このとき基準札の位置は確定します。
(4)確定札を含まない札から成る２枚以上のストリング（列）に対して、この手順を適用します。こうして、基準札の位置が一つずつ確定していきます。

以下の説明は特に理解しなくても、この方法は使えます。
「再帰呼び出し」というのは、呼び出すプログラムと、呼び出されるプログラムが同一である場合の手続きを指します。実行が終了していないのに、未完了の部分に対してプログラムを再適用しようとするものです。会社が１つしかないのに、下請け発注をして、その注文書を自分自身が受け取って「下請け会社になりすまし」をするという、プログラミング上のテクニックです。クイックソートは、再帰呼び出しが可能なコンピューターでのみ実行できます（現在は、すべてのパソコンンで可能ですが）。

No.5 回答者： Ishiwara 回答日時： 2008/07/17 11:08

「並び替え」ではありません。

「並べ替え」です。
並べ替え問題は、コンピューターの世界で詳しく研究されています。キーワード「クイックソート」で調べてみてください。これなら７回以内でできると思います。

クイックソートの原理：
(1)左端を「基準札」、右端を「対象札」とする。
(2)２つの札の大小関係が正しければ、対象札の隣（基準札寄り）を次の対象札とする。
(3)基準札と対象札が隣り合ってしまえば、この２つについては完成なので、未完成部分について(1)に戻る。
(4)もし(2)で大小関係が逆であれば、両札を交換して(2)から再実行する。ただし、この交換では「基準札」「対象札」の資格は各札が背負ったまま移動するので、両札の左右関係は反転する。

No.4 回答者： noname#161636 回答日時： 2008/07/17 00:19

この問題に関して別のアプローチを試みました。

Jリーグなどで使われるリーグ対戦表（総当り戦形式）を用いて、比較すべき数字の組み合わせを表に○印してみるというものです。

この表を大きい数字から数字順に並べ替えて作図しますときわめて特徴的な図形が現れます。
具体的には表の斜線部分に規則的に印される結果になります。

現在ANo3さんによりますと12枚のカードを大きい順に並べ替えるのに必要な手順数は29手順ということですが、このリーグ対戦表からは13枚以上のカードを並べ替える場合の手順数が感覚的に類推できそうな図表が得られます。

数学的に証明しうるのかどうかは解りませんが、専門家の方または詳しい方がありましたらご教示願えるとありがたく思います。

質問者さまの提起された質問に触発されてこの場をお借りして質問させていただきましたがご了承ください。

なお質問者さまは見たところ受験勉強中のかたとお見受けしました。
この問題には深入りなさらずに、気分転換程度になさってください。見当違いでしたらお許しください。

No.3 回答者： mistery200 回答日時： 2008/07/16 19:22

http://oshiete1.goo.ne.jp/qa4044940.html

に同じ質問と答えがあります。
「１２枚のカードを２９回ができるかどうか」
まで議論されてます。

この回答へのお礼

ありがとうございます！

お礼日時：2008/07/17 06:01

No.2 回答者： dongri5656 回答日時： 2008/07/16 18:26

「並べ替え」でしょ。

そんな日本語はありませんから。

No.1 回答者： noname#66332 回答日時： 2008/07/16 17:54

[20]

[30]
[10]
[25]
[15]

これを7回の比較で「どう」並び替えるんですか？
問題の意味を教えて下さい<m(__)m>