【情報I】探索と整列のアルゴリズムを図解で総まとめ—線形探索・二分探索・選択ソート・バブルソート｜武蔵野個別指導塾

並んだ数を追う図と4つの例題で、線形探索・二分探索・選択ソート・バブルソートの手順を確かめます。比較回数の数え方や、データが増えたときの計算量まで、自分で説明できるように進めましょう。

よくあるのは、駅前の本屋の参考書の棚で、背表紙を左から順に見ているうちに、「番号順に並んでいるなら、途中から探したほうが速そうなのに、どうして最初から見るのだろう」と立ち止まる場面です。実際には、棚が何の順序で並んでいるかによって、使える探し方が変わります。題名を探しているのに、値段の順序を頼りに半分を見ないことにすると、目当ての本を見落とすかもしれません。

情報Iの探索と整列も、この「順序を利用できるか」という問いから考えられます。探索は目的のデータを見つける処理、整列は決めた順序にデータを並べる処理です。名前を暗記するだけでは、途中のリストや比較回数を問われたときに手が止まります。どの場所を比べ、どの範囲が残り、何が確定したのかを紙に書くと、処理の流れを追えるようになります。小さなリストで手順を確かめてから、データが増えたときの仕事の量まで考えていきましょう。

この単元で身につけること

• 探索と整列の目的を区別します。目的の値の位置を返すのか、リスト全体の並びを変えるのかを、問題文から読み取ります。
• 線形探索を先頭から追います。一致したときに終了する場合と、最後まで見つからない場合を分けて、照合した要素の数を数えます。
• 二分探索の前提と範囲の更新を説明します。昇順に整列したデータで中央を調べ、答えの候補が残る側だけを次の探索範囲にします。
• 選択ソートとバブルソートを区別します。最小値を選んで置く方法と、隣同士を比べて交換する方法について、1巡後の変化を追います。
• 比較回数の増え方から計算量を考えます。ある入力での正確な回数と、要素数が大きくなったときの増え方を混同せずに説明します。

前の単元で学んだリストの添字、条件分岐、繰り返しを、目的のあるまとまった手順として組み合わせるのがこの単元です。Pythonでは添字が0から始まるので、先頭から何番目かと、プログラムが返す添字を別々に書く習慣も身につけましょう。

基本の考え方

探索は「どこにあるか」、整列は「どんな順にするか」

たとえば、リスト［18, 7, 25, 12, 30］から12を探すと、先頭から4番目、添字では3にあります。この位置を求めるのが探索です。一方、同じリストを［7, 12, 18, 25, 30］にするのは整列です。小さいものから大きいものへ並べる順序を昇順、大きいものから小さいものへ並べる順序を降順といいます。ここでは数値を昇順にする場合を扱います。

整列では、値を小さい順に書き直せばよいだけではありません。元の値と個数を保ちながら並べ替える必要があります。交換のつもりで一方の値を上書きし、もう一方を失ってしまったら、整列に成功したとはいえません。また、本の情報のように番号と題名が組になっているなら、番号で並べ替えるときにも対応する題名を一緒に動かす必要があります。順序の基準となる項目をキーと呼びます。

探索で同じ値が複数ある場合は、どれか1つの位置が必要なのか、最初の位置なのか、すべての位置なのかで終了条件が変わります。以下の線形探索は最初の一致で終了し、二分探索は途中で見つかった1つの位置を返します。同じ値を見つける処理でも、必ず同じ位置を返すわけではない点に注意しましょう。

線形探索と二分探索では、見なくてよい理由が違う

線形探索は、先頭から1つずつ順に、探す値と一致するかを調べます。データが未整列でも使えます。図1のように12を探すなら、18、7、25、12の順に照合します。12で一致したので、その右にある30を調べる必要はありません。ここで見なくてよい理由は、求めていた答えがすでに見つかったからです。

図1の赤い枠は一致した要素、矢印は調べる順序です。値の大小に応じて飛び越える処理はありません。もし探す値が存在しなければ、最後の要素まで調べて、そこで初めて「見つからない」と判断できます。要素数をnとすると、最初に見つかる場合は1回、最後に見つかる場合や存在しない場合はn回の照合です。ただし、空のリストでは照合は0回です。

二分探索は、探索するキーについて整列済みであることを利用します。昇順のリストの中央が15で、探す値が19なら、中央の15とそれより左の値はすべて19より小さいので候補から外せます。右側だけを次の探索範囲にして、再び中央を調べます。この場合に見なくてよい理由は、順序から「そこには答えがない」といえるからです。

ここでは、左端と右端をともに候補に含める方式に統一します。左端の添字をleft、右端をrightとし、中央は（left + right）を2で割った商です。Pythonでは整数同士の // によってこの商を求めます。中央の値より目標が大きければleftを中央の添字 + 1にし、小さければrightを中央の添字 − 1にします。すでに不一致と判明した中央を残さないことが、範囲を必ず縮めるための決まりです。

回数は「何を1回と数えるか」から決める

探索の比較回数には、問題の数え方を確認する必要があります。ここでは、候補の要素を1つ取り出して目的の値と照合することを1回と数えます。二分探索のコードで一致の判定と大小の判定を両方実行しても、同じ中央要素の照合は1回です。比較演算子が実際に実行された回数や、繰り返し条件の判定回数を数える問題なら、別に数え直します。

計算量は、入力の大きさが増えたときに処理の量がどの程度増えるかを表す考え方です。線形探索の最悪時の照合回数はnなので、増え方はO(n)と表せます。二分探索は範囲をほぼ半分ずつにするため、最悪時の増え方はO(log n)です。Oは大まかな増え方を表す記号で、「どの入力でも必ず同じ回数になる」という意味ではありません。二分探索でも最初の中央で見つかれば1回です。

この方式の二分探索では、要素数が1、3、7、15、31のとき、最悪時の照合回数はそれぞれ1、2、3、4、5回です。要素数が2ᵏ − 1なら最悪時はk回となります。たとえば31個から63個へ増えても、最悪時は5回から6回への増加です。厳密な回数が必要な問題では、単に「半分だからlog」と書くのではなく、指定された中央の取り方と終了条件で実際に範囲を追いましょう。

また、回数が少ない方法を選ぶには準備も考えます。未整列のデータから1度だけ探すなら、整列してから二分探索するための処理が、線形探索だけで済ませる処理を上回る場合があります。すでに整列しているか、何度も探索するか、データの追加が多いかによって選び方が変わります。

例題で解き方を確かめる

例題1　線形探索の位置と照合回数

リスト［18, 7, 25, 12, 30］から12を線形探索します。最初の一致で終了するとき、返す添字と照合回数を求めましょう。見つからない場合には−1を返すことにします。

1. 添字を0、1、2、3、4と書き添えます。値そのものと、値が入っている位置を区別するためです。
2. 添字0の18、添字1の7、添字2の25を順に照合します。どれも12ではないので、次の要素へ進みます。
3. 添字3の12を照合したところで終了します。一致後に照合を続けないので、最後の30は回数に含めません。

答え：返す添字は3、先頭から4番目で、照合回数は4回です。

次のプログラムでは、foundの初期値を−1にしておきます。見つかったときだけ添字に置き換えることで、最後まで見つからない場合も同じ変数で表せます。

a = [18, 7, 25, 12, 30]
target = 12
found = -1
checks = 0
for i in range(len(a)):
    checks += 1
    if a[i] == target:
        found = i
        break
print(found, checks)

出力は 3 4 です。breakは繰り返しを終了させます。−1はこのプログラムで定めた「見つからない」という結果であり、そのままリストの添字に使う値ではありません。Pythonで a[-1] とすると最後の要素を指すため、結果が−1かどうかを確認してから要素を参照する必要があります。

例題2　二分探索の候補範囲を追う

昇順のリスト［3, 7, 11, 15, 19, 23, 27］から19を二分探索します。中央の添字は両端の添字の平均を切り捨てた整数とします。各回の中央の値と、照合回数を求めましょう。

1. 最初の範囲を添字0から6までとします。中央の添字は3、値は15です。19は15より大きいので、次の範囲を4から6までにします。
2. 次の中央の添字は5、値は23です。19は23より小さいので、次の範囲を4から4までにします。中央の23も候補から外す点に注意します。
3. 最後の中央の添字は4、値は19です。一致したので探索を終了します。候補が1個でも、まだ照合していなければ処理が必要です。

答え：中央の値は15、23、19の順で、添字4を3回の照合で見つけます。

図2のように、位置を動かさずに候補の枠だけを絞ると、添字を振り直す誤りを防げます。灰色は候補から外れた要素、赤い枠はその回に照合する中央要素、紺色の枠は残っているほかの候補です。

図2の最下段では、候補が19だけになっています。この1個を調べる前に終了すると、存在している値を見落とします。コードの繰り返し条件をleftがright以下である間とするのは、この最後の1個も調べるためです。

a = [3, 7, 11, 15, 19, 23, 27]
target = 19
left, right = 0, len(a) - 1
found, checks = -1, 0
while left <= right:
    mid = (left + right) // 2
    checks += 1
    if a[mid] == target:
        found = mid
        break
    elif a[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
print(found, checks)

出力は 4 3 です。目標を20に変えると、15、23、19を照合したあと、leftは5、rightは4になります。候補範囲が空になり、出力は -1 3 です。見つからない場合も、両端が逆転するという明確な終了条件があります。

例題3　選択ソートで最小値を置く

リスト［4, 2, 3, 1］を選択ソートで昇順に整列します。未整列部分の最小値の位置を見つけて、その部分の先頭と交換する方法です。各巡の結果と、要素同士の比較回数を求めましょう。

1. 最初は4個すべてが未整列です。先頭の4を最小値の候補とし、2、3、1と順に比べます。比較は3回で、最小値1と先頭の4を交換すると［1, 2, 3, 4］になります。
2. 次は先頭の1を確定済みとして外し、残る［2, 3, 4］の最小値を探します。2を候補として3、4と比べるので2回です。最小値はすでにその部分の先頭にあり、交換は行いません。
3. 残る［3, 4］で1回比較します。3はすでに正しい位置です。最後の1個は自動的に位置が決まるので、さらに最小値を探す必要はありません。

答え：各巡の結果はすべて［1, 2, 3, 4］で、比較回数は3 + 2 + 1 = 6回です。

最初の交換で偶然全体が整列しても、この選択ソートには全体の整列を検出して止まる処理がないので、残る比較も実行します。「見た目が整った時点」と「アルゴリズムの終了時点」を区別しましょう。

a = [4, 2, 3, 1]
checks = 0
for i in range(len(a) - 1):
    m = i
    for j in range(i + 1, len(a)):
        checks += 1
        if a[j] < a[m]:
            m = j
    if m != i:
        a[i], a[m] = a[m], a[i]
print(a)
print(checks)

出力は1行目が [1, 2, 3, 4]、2行目が 6 です。mは最小値そのものではなく、その位置を保存しています。大小を比べるときは a[m] として値を取り出し、最後の交換ではmを位置として使います。

例題4　バブルソートで隣同士を交換する

同じリスト［4, 2, 3, 1］をバブルソートで昇順に整列します。左から右へ隣同士を比べ、左が大きいときに交換します。1巡ごとに右端の確定部分を広げ、途中で打ち切る工夫は入れないものとします。

1. 1巡目は4と2、4と3、4と1の順に比べます。交換のたびに4が右へ移り、［2, 3, 1, 4］になります。右端に最大値が確定します。
2. 2巡目は確定した4を除きます。2と3は交換せず、3と1を交換すると［2, 1, 3, 4］です。右から2番目の3も確定します。
3. 3巡目は2と1を交換します。［1, 2, 3, 4］となり、整列が終了します。比較回数は巡ごとに3回、2回、1回です。

答え：1巡目は［2, 3, 1, 4］、2巡目は［2, 1, 3, 4］、3巡目は［1, 2, 3, 4］で、比較は6回、交換は5回です。

a = [4, 2, 3, 1]
checks, swaps = 0, 0
for end in range(len(a) - 1, 0, -1):
    for j in range(end):
        checks += 1
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swaps += 1
print(a)
print(checks, swaps)

出力は1行目が [1, 2, 3, 4]、2行目が 6 5 です。range(end)の最後のjはend − 1なので、右隣のj + 1はendになります。確定した部分に入り込まず、未整列部分の右端まで比べられます。

選択ソートとこのバブルソートでは、n個の要素に対する比較回数は（n − 1）+（n − 2）+ … + 1、すなわちn(n − 1)/2です。4個では6回、8個では28回、16個では120回になります。要素数を2倍にしても比較回数はちょうど4倍にはなりませんが、大きなnではおよそ4倍へ近づくため、増え方をO(n²)と表します。交換回数は入力によって変わり、比較回数と同じとは限りません。

つまずきやすいところと直し方

誤り1　未整列のリストにも二分探索を使う

誤った書き方は、「［18, 7, 25, 12, 30］の中央は25なので、12を探すときは左半分だけを見る」です。どこが違うかというと、右側にある値がすべて25以上とはいえない点です。実際には探す12が右側にあるため、その範囲を捨てると答えを失います。

正しい書き方は、「未整列なので線形探索を使う。二分探索を使うなら、先に探索のキーについて整列する」です。整列後の添字は元のリストの添字と変わる場合があります。元の位置が必要なら、元の添字も値と組にして保持するなど、位置の対応を残す必要があります。

誤り2　中央を候補に残したまま範囲を更新する

誤った書き方は、「中央より目標が大きければleftをmidにする」です。どこが違うかというと、中央がすでに目標と異なるのに候補に残り、場合によっては範囲が縮まらない点です。たとえば［3, 7］から7を探すと、leftが0、rightが1、midが0になります。leftをmidに戻すと、同じ3を何度も調べ続けます。

正しい書き方は、この両端を含む方式では「leftをmid + 1にする」です。逆側へ進む場合はrightをmid − 1にします。終了条件と更新規則は組で理解しましょう。右端を候補に含めない別の方式もありますが、片方の規則だけを混ぜると境界で誤りが起きます。

誤り3　1巡で確定する側を取り違える

誤った書き方は、「左から右へ進むバブルソートは、1巡で先頭に最小値が来る」です。どこが違うかというと、隣同士の交換では、大きい値が次の比較へ引き継がれて右へ移動する点です。正しい書き方は、「この向きのバブルソートは、1巡で右端に最大値が確定する」です。逆向きに走査する実装では確定する側も変わるので、名称だけで決めずに比較の向きを読みます。

図3のように、同じ［4, 2, 3, 1］でも、選択ソートの1巡目は先頭へ最小値1を置き、今回のバブルソートの1巡目は右端へ最大値4を運びます。緑の枠は、その巡で新たに位置が確定した要素です。選択ソートの右側も結果的に昇順ですが、手順として確定させたのは先頭の1です。

比較と交換の混同も、この違いに関係します。すでに昇順の4個を同じコードで整列しても、両方式とも比較は6回行いますが、交換は0回です。バブルソートに「1巡で交換がなければ終了する」という工夫を加えると、この場合は最初の3回の比較で終了できます。したがって、バブルソートという名前だけを見て最良時の回数を断定せず、早期終了があるかまで確かめます。

練習問題

練習1　見つからない線形探索

［9, 4, 14, 6, 20］から8を、例題1と同じ線形探索で探します。照合する値の順序、返す結果、照合回数を求めましょう。また、目標を6に変えた場合の添字と照合回数も求めてください。値が目標より大きいという理由だけで途中終了できるかも考えます。

練習2　二分探索の最後の候補

［2, 5, 8, 11, 14, 17, 20, 23］から20を、例題2と同じ方式で探します。各回のleft、right、midと、中央の値を順に書き、返す添字と照合回数を求めましょう。さらに、21を探した場合にはどの状態で終了するかを答えてください。

練習3　1巡の違い

［5, 1, 4, 2］を、例題3の選択ソートと例題4のバブルソートで、それぞれ1巡だけ処理します。各方式について、1巡後のリスト、比較回数、交換回数を求めましょう。バブルソートは左から右へ進め、交換するたびに更新されたリストを使います。

練習4　データが増えたときの回数

要素数15と31について、線形探索と例題2の二分探索の最悪時の照合回数を求めましょう。また、例題3の選択ソートで15個と31個を整列するときの比較回数を求めてください。最後に、この2つの整列の比較回数が正確に4倍の関係になるかを確かめましょう。

答えと解説

練習1：8を探す場合は9、4、14、6、20の順に照合し、結果は−1、照合回数は5回です。6を探す場合は添字3、照合回数は4回です。未整列のため、9が8より大きくても、その後に8がないとは判断できません。

練習2：20を探す場合、（left, right, mid）は（0, 7, 3）、（4, 7, 5）、（6, 7, 6）と変わります。中央の値は11、17、20で、結果は添字6、照合回数は3回です。21を探す場合はさらに（7, 7, 7）で23を照合し、その後leftが7、rightが6となって終了します。結果は−1、照合回数は4回です。

練習3：選択ソートは最小値1と先頭の5を交換して［1, 5, 4, 2］となり、比較3回、交換1回です。バブルソートは［1, 5, 4, 2］、［1, 4, 5, 2］、［1, 4, 2, 5］と変わり、比較3回、交換3回です。途中で同じ並びになっても、その後に行う比較が違うため、1巡後の状態は一致しません。

練習4：線形探索は15回と31回、二分探索は4回と5回です。選択ソートは15 × 14 ÷ 2 = 105回、31 × 30 ÷ 2 = 465回です。105の4倍は420なので、正確に4倍ではありません。今回は要素数自体もちょうど2倍ではなく、さらに比較回数の式にはnから1を引く項があるので、大まかな増え方と具体的な回数は分けて扱います。

次の単元へのつながりと家庭での確かめ方

探索と整列は、データベースで必要な記録を探したり、数値を順序づけて分析したりするときの土台です。整列によって後の探索を速くできるように、ある処理の前に準備をすることで、全体の効率が変わる場面はほかの単元にも現れます。シミュレーションでも、同じ処理を多くの対象に繰り返すときには、1回分の手順と全体の回数を分けて考えます。

家庭では、それぞれ5分ほどで次の確認ができます。1つ目は、7枚の紙に異なる数を書いて昇順に並べ、目標を決めて二分探索をする方法です。中央を指さすたびに、左右のどちらを外せるかを声に出します。目標がない場合も1回試すと、終了条件まで確かめられます。

2つ目は、4枚の紙を並べ、選択ソートとバブルソートを1巡ずつ行う方法です。同じ初期状態へ戻してからそれぞれ試し、比較のたびに点を、交換のたびに丸を書けば、2種類の回数を区別できます。保護者の方が一緒に確かめる場合は、お子さまに「どの位置がもう決まったのか」を説明してもらうと、最終結果だけでは見えない理解を確かめられます。

個別指導で手順が止まったときは、まず値と添字の区別に戻り、次に1回分の比較前後で変数がどう変わるかを確かめます。全体を一度に追わせるのではなく、候補範囲や確定部分を本人が指せるところから、繰り返し全体へつなげます。

まとめ

棚から1冊を見つけることも、リストを順序づけることも、終わった形だけなら簡単に確かめられます。しかし、情報Iで説明したいのは、そこへたどり着くまでにどこを調べ、何を根拠に次へ進んだかです。途中の状態を1つ書くだけで、覚えた名前が実際に動かせる手順へ変わります。

答えが合っていても、候補から外した範囲に答えが残っていたなら、その方法には修正が必要です。反対に、途中で止まっても、最後に正しく確定できた場所がわかれば、そこから考え直せます。速い探索を支えるのは、調べなかった場所に答えがないと言い切れる根拠です。