ソートは何問で終わる？｜項目数別の質問数の早見表と少なく済む仕組み

項目数別の質問数の早見表

推しソート メーカーで、引き分けを一度も使わなかった場合の質問数の最大を項目数ごとにまとめました。比較のために、すべての組み合わせを 1 回ずつ聞く方法（総当たり・一対比較）の質問数と、どんな並べ方をしても最悪の場合にはこれ以上かかる「理論上の下限」も並べています。

項目が増えるほど、総当たりとの差は大きく開きます。10 個では総当たりの 6 割ほどですが、47 個では約 5 分の 1、100 個では約 8 分の 1 で済みます。表の「最大」はいちばん多くかかった場合の数で、実際には答え方によって少し早く終わることがほとんどです。好みがはっきりしていて引き分けを使わない場合でも、47 個なら 210 問前後、100 個なら 560 問前後で終わることが多くなります。

総当たり（一対比較）だと質問数はどう増える？

すべての組み合わせを 1 回ずつ比べる総当たりの質問数は、項目数 ×（項目数 − 1）÷ 2 です。リーグ戦の試合数と同じ計算で、10 個なら 45 問、20 個なら 190 問、47 個なら 1,081 問になります（リーグ戦の試合数の数え方は総当たりの試合数と試合順の作り方でも説明しています）。

総当たりは項目数の 2 乗に近いペースで増えるので、項目が 2 倍になると質問はおよそ 4 倍になります。30 個を超えたあたりから、一人で最後まで答えるのは現実的ではなくなります。そのぶん、すべての組み合わせを実際に聞くので、勝った回数を数えれば「好みに矛盾があるか」まで分かるのが総当たりの良いところです。

ソートは、聞かなくても分かる組み合わせを省いて質問を減らします。「A は B より好き」「B は C より好き」と答えたなら、「A と C はどっち？」は聞かずに A を上とみなします。この「好きの順番はつながっている」という前提を置くことで、項目数 × log₂（項目数）くらいのペースでしか質問が増えなくなります。

マージソートの仕組み｜4人の例で数えてみる

推しソート メーカーの並べ方はマージソートです。「並んだ列どうしを、先頭どうしを比べながら 1 本につなぐ」作業を繰り返します。A・B・C・D の 4 人で流れを追ってみましょう。

1. 1

   1 回目：2 人ずつの組を作る

   A と B、C と D を比べます（2 問）。A＞B、D＞C と答えたとすると、「A, B」と「D, C」という 2 本の列ができます。

2. 2

   2 回目：2 本の列の先頭どうしを比べる

   列の先頭どうし、A と D を比べます。A＞D なら、全体の 1 位は A に決まります。2 位はまだ残っている先頭の B と D で決めます。

3. 3

   残った先頭どうしを比べ続ける

   B と D を比べ、D＞B なら 2 位は D。最後に B と C を比べて順位が確定します。ここまでで 2 ＋ 3 ＝ 5 問。総当たりなら 6 問なので、1 問少なく済みました。

4. 4

   片方の列が空になったら、質問なしで並ぶ

   2 回目で A と B が D に続けて勝った場合、A, B が並んだ時点で左の列が空になります。D と C はもう順番が決まっているので、そのまま後ろにつなぐだけ。この場合は 2 ＋ 2 ＝ 4 問で終わります。

項目が増えても同じことを繰り返します。1 人ずつの列を 2 本ずつつないで 2 人の列に、2 人の列をつないで 4 人の列に…と、列の長さが倍々になっていき、最後に 1 本になったところで完成です。長さ a と b の列をつなぐのにかかる質問は最大で a ＋ b − 1 問なので、全体の質問数は「つなぐ段の数（約 log₂ 項目数）× 項目数」くらいに収まります。

「最大あと何問」が途中で急に減るのはなぜ？

推しソート メーカーの質問画面には「第◯問（最大あと◯問）」と進み具合のバーが出ます。この「最大あと何問」は、ここから先の答えがいちばん質問の多くなる形になった場合の数です。そのため、答え方によっては一気に減ることがあります。

• 片方の列が連勝したとき：上の例のように、片方の列の項目が続けて勝つと、その列が先に空になり、もう片方の残りは質問なしで後ろに並びます。好みがはっきりしているほど、この「質問なしで決まる」場面が増えます。
• 引き分けを選んだとき：引き分けにした 2 つは同じ順位の 1 つのまとまりになり、以後は 1 つとして比べられます。比べる相手が 1 つ減るので、残りの最大も減ります。
• 逆に、ほぼ交互に勝つと最大に近くなる：2 本の列の項目が交互に勝つような答え方だと、最後まで先頭どうしを比べ続けるので、質問数は最大に近づきます。

極端な例では、10 個をすべて引き分けにすると 9 問で終わります。もちろん全員同率の結果になるので意味はありませんが、引き分けがそれだけ質問を減らすことが分かります。引き分けの使いどころはソートの引き分けはどう使う？で詳しく説明しています。

質問を減らして最後まで答えきるコツ

• 項目をしぼる：質問数を減らすいちばん確実な方法です。100 個を 50 個にすると、最大 589 問が 245 問と半分以下になります。よく知らない項目、明らかに下位になる項目は始める前に外しましょう。
• ソートを分ける：全キャラ・全曲を 1 回でやるより、「作品ごと」「アルバムごと」に分けてから、それぞれの上位だけでもう一度ソートするほうが、1 回あたりの負担は軽くなります。ただし分けた場合、別のグループどうしの下位の順番は比べられません。
• 本当に決められないときだけ引き分けにする：引き分けは質問を減らしますが、一度同率にしたものは最後まで同じ順位のままです。迷ったら直感で選び、気になったら後でやり直すほうが、順位の情報は多く残ります。
• 途中保存を使って休む：長いソートは、疲れてくると答えが雑になります。答えはその都度保存されるので、区切りのよいところで閉じて、続きは後で再開できます。

自作ソートの作り方そのものは推しソートの作り方で、項目リストの作り方とあわせて説明しています。

よくある質問

推しソートは何問で終わりますか？

項目数で決まります。推しソート メーカーで引き分けを使わない場合の最大は、10 個で 27 問、20 個で 73 問、30 個で 119 問、47 個で 220 問、100 個で 589 問です。答え方や引き分けによって、これより少なく終わることがほとんどです。

全部の組み合わせを聞かないのに、なぜ順位が決まるのですか？

「A は B より好き」「B は C より好き」なら「A は C より好き」とみなして、聞かなくても分かる組み合わせを省いているからです。並べた列どうしを先頭から比べてつないでいくマージソートという方法で、47 個なら全組み合わせ 1,081 問の約 5 分の 1 で終わります。

総当たりの質問数はどう計算しますか？

項目数 ×（項目数 − 1）÷ 2 です。10 個で 45 問、20 個で 190 問、50 個で 1,225 問になり、項目が 2 倍になるとおよそ 4 倍に増えます。

47 都道府県のソートは何分くらいかかりますか？

最大 220 問なので、1 問 3 秒で答えると約 11 分です。実際には 210 問前後で終わることが多く、引き分けを使えばさらに少なくなります。途中で閉じても続きから再開できます。

「最大あと何問」の数字が急に減ったのはなぜですか？

片方の列の項目が続けて勝って列が空になると、もう片方の残りは質問なしで順番が決まるためです。引き分けを選んだときも、2 つが 1 つのまとまりになって比べる相手が減るので、残りの最大が減ります。