整列と探索の問題の解き方

整列は、1周ごとに配列を書き直す

次はバブルソート（隣どうしを比べて、大きい方を後ろへ送る整列）です。

○bubbleSort(整数型の配列: data)
  整数型: n ← dataの要素数
  整数型: i, j, tmp
  for (i を n から 2 まで 1 ずつ減らす)
    for (j を 1 から i - 1 まで 1 ずつ増やす)
      if (data[j] > data[j + 1])
        tmp ← data[j]
        data[j] ← data[j + 1]
        data[j + 1] ← tmp
      endif
    endfor
  endfor

data が {5, 3, 4, 1} のとき、外側のループ（i）の1周ごとに書き直すと、こうなります。

はじめ :  5  3  4  1
i = 4  :  3  4  1  5   比較3回・交換3回
i = 3  :  3  1  4  5   比較2回・交換1回
i = 2  :  1  3  4  5   比較1回・交換1回

1周ごとに、その周で一番大きい値が右端に決まっていきます（i = 4 の周で 5、i = 3 の周で 4）。 決まった値に印を付けておくと、次の周で比べる範囲が1つ減る理由が目で分かります。

内側のループの中まで1回ずつ書くのは、比較や交換の回数を聞かれたときだけで十分です。 結果の並びだけを聞かれているなら、1周ごとの行だけを書けば時間を節約できます。

比較と交換は、数える場所を決めてから数える

上の例では、比較は合わせて 3 + 2 + 1 = 6 回、交換は 3 + 1 + 1 = 5 回です。 ここで間違えやすいのは、何を1回と数えるかです。

• ・比較は、if (data[j] > data[j + 1]) が実行された回数。結果が true でも false でも1回
• ・交換は、if の中に入った回数。比較の回数とは別に数える
• ・問題によっては、プログラムの中に count ← count + 1 のような行が置かれています。 その場合は、その行が何回実行されたかだけを数えます。自分の考える「比較」ではなく、行の位置が正解を決めます

比較の回数は、データの並びに関係なく内側のループの回数で決まることが多く、交換の回数はデータの並びで変わります。 選択肢に同じ比較回数が並んでいたら、交換回数の方を数えて絞り込みます。

二分探索は、探す範囲を毎回書く

二分探索は、小さい順に並んだ配列で、真ん中の値と比べて探す範囲を半分ずつに狭めていく探し方です。 並んでいない配列には使えません。問題文で「昇順に整列済み」と書かれているかを確かめてください。

{2, 5, 8, 12, 16, 23, 38} から 23 を探すとき、範囲はこう狭まります（真ん中は小数点以下を切り捨て）。

要素番号:  1  2  3  4  5  6  7
値      :  2  5  8 12 16 23 38

1回目: 範囲 1〜7、真ん中 4（値 12）。12 < 23 なので右側に絞る
2回目: 範囲 5〜7、真ん中 6（値 23）。見つかった

2回目の範囲が 4〜7 ではなく 5〜7 から始まっていることに注目してください。 真ん中の要素番号 4 はもう比べ終わっているので、次の範囲に含める必要がありません。 含めたままにすると、見つからないときに同じ要素を何度も比べて、ループが終わらなくなることがあります。

穴埋めで範囲の更新の式を選ぶ問題は、見つからない値で最後まで追ってみると確かめられます。 上の配列で 20 を探して、範囲が空になってループが終わるか（終わらずに同じ範囲を繰り返さないか）を見ます。

何回で終わるかは、計算量で答える問題もある

「要素数が2倍になると比較回数はおよそ何倍か」のように、回数を n の式で聞く問題もあります。 数え方は計算量の問題の解き方にまとめています。

ほかの分野の解き方

• 配列の問題の解き方
• 計算量の問題の解き方
• 擬似言語のトレースのやり方