高校情報I バブルソート—隣同士の交換を追って一巡で確定する位置を説明する｜武蔵野個別指導塾

左から隣接するカードを交換する過程を追い、一巡後の確定位置と交換なしの停止条件を結びつけます。

よくあるのは、高校生がカードの列を一巡した時点で、配列全体が整列したと考える場面です。隣同士を左から比べると大きいカードは右へ進みますが、小さいカードが一巡で左端まで戻るとは限りません。どの位置が確定したかを区別すると、途中の列も停止の条件も説明できます。

何を答える問題か

出方の一つは、数の列と比較方向を指定し、1回の比較や1巡の後の配列を書く問題です。比較する位置と交換前後の値を分けて記録します。もう一つは、途中の状態から次に比べる組、確定した範囲、残りの処理を求める問題です。さらに、交換がなかったという記録を使い、そこで処理を止めてよい理由を問う場合もあります。

ここでは整数のカードを小さい順、つまり昇順に並べます。添字は0から始め、リストの長さをnとします。空の列も1枚の列も受け入れます。同じ数のカードは交換しません。比較回数は隣接する2枚の値を比較した回数、交換回数はその2枚を入れ替えた回数です。出力は整列した新しいリスト、比較回数、交換回数の順とします。入力リストそのものは変更しません。未発見という値は整列の仕様にはありません。

入力は整数のリストとし、文字列や整数以外の要素は対象外です。以下の関数は外部入力や外部サービスを使わず、時間制限も設けません。対象外の型に対する例外や時間切れ、外の道具の失敗を処理する機能は持たないため、そうした場合に整列結果を返す保証はありません。これらと、仕様内の空リストという正当な入力を混同しないことが重要です。

右端に運ばれる値

隣接する2枚を比べ、左が右より大きいときに交換します。左から右へ次々と比較すると、比較済みの範囲で最大の値が右側のカードとして残り、次の組へ引き継がれます。図1のように、1巡の終了時には、その巡回の対象範囲で最大の値が右端に置かれます。

図1の例は [4, 1, 3, 2] です。4は1、3、2と順に交換され、右端へ到達します。残った [1, 3, 2] はまだ昇順ではありません。次の巡回では確定済みの右端を除いて比べればよく、その対象の最大値が次の右端へ置かれます。

この説明は、反復の前提と保たれる条件を分けると明確です。入力は有限個の整数です。各巡回の前には、右側の確定部分が昇順であり、そこに置かれた値は未確定部分のどの値以上でもあります。1巡で未確定部分の最大値をその右端に置くと、確定部分が1位置広がり、この条件が保たれます。交換は元の要素を入れ替えるだけなので、要素の個数と内容は変わりません。

比較には厳密な大小関係を使います。等しい2枚を交換しなければ、同じ値のカード同士が互いを追い越すことはありません。番号札などを付けて区別した場合も、等しい値の元の順序が保たれます。これを安定な整列と呼びます。ただし、単なる整数の表示だけから、同値のカードの順番が保たれたかどうかを見分けることはできません。

基本例題：4枚のカード

カードの値を左から [4, 1, 3, 2] とします。添字0から始め、左から右へ比較し、大きい左の値を交換します。各巡回の終了後の列と、最後のリスト、比較回数、交換回数を答えてください。早期終了を使い、最後に比較対象が1枚になったときは新しい巡回を行いません。

まず手で追います。図2のように、最初の巡回では添字0と1、1と2、2と3を順に比べます。交換後の値を次の比較へ使うことが大切です。

図2の各段階を表にすると、次のようになります。比較の相手は初期状態のまま固定されません。

比較位置  比較する値  操作    操作後
0と1      4と1        交換    [1, 4, 3, 2]
1と2      4と3        交換    [1, 3, 4, 2]
2と3      4と2        交換    [1, 3, 2, 4]

2巡目の対象は先頭3枚です。1と3は交換せず、3と2は交換して [1, 2, 3, 4] となります。3巡目は1と2を比較し、交換がないので終了します。比較は3回、2回、1回の計6回、交換は3回、1回、0回の計4回です。結果には元の4枚が各1枚ずつ残り、左から右へ値が減る箇所もありません。

次の関数で同じ手順を実行します。入力をコピーしてから作業し、記録を一緒に返します。

def bubble_sort(cards):
    a = cards.copy()
    comparisons = 0
    swaps = 0
    for end in range(len(a) - 1, 0, -1):
        changed = False
        for j in range(end):
            comparisons += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
                changed = True
        if not changed:
            break
    return a, comparisons, swaps

print(bubble_sort([4, 1, 3, 2]))

実行環境はPython 3.14.8です。入力 [4, 1, 3, 2] の期待出力と実際の出力はともに ([1, 2, 3, 4], 6, 4) です。

def は処理の入口を作ります。copy は元のカード列と作業用の列を分けます。2つの数え手を0にし、end には今回の未確定部分の右端の添字を入れます。range は右端を含む位置から1まで減るので、長さ4なら3、2、1の順です。各巡回の初めに changed を偽に戻します。

内側の j は0から end - 1 まで動き、j + 1 が右端を越えないようにします。比較を1回数え、左の値が大きい場合に2つの値を同時に入れ替え、交換回数と記録を更新します。1巡して記録が偽のままなら break で外側の反復を抜けます。最後にリストと2つの回数を返します。空や1枚では外側の範囲が空なので比較せず返ります。

交換がない巡回では、対象内の隣り合うすべての組で左が右以下です。したがって対象部分は昇順です。先に確定した右側との境界も保たれているので全体が昇順になり、停止できます。交換が続いても end は毎回1ずつ減り、有限回で終わります。例の実行は実装の照合であり、一般の正しさはこの不変条件と終了理由で説明します。

標準例題：同じ値と交換なし

値が [2, 2, 1, 3] のカードを同じ仕様で整列します。1巡目は2と2を交換せず、次の2と1を交換し、最後の2と3を交換しません。結果は [2, 1, 2, 3] です。2巡目では2と1を交換し、2と2は交換しません。結果は [1, 2, 2, 3] です。3巡目は1と2を比較して交換がなく、終了します。

手計算の期待値は ([1, 2, 2, 3], 6, 2) です。上の関数にこの入力を渡した実際の出力も同じです。2が2枚、1と3が各1枚という元の枚数を保ち、隣接する値も昇順です。等しい2枚を入れ替えない条件を > で表している点が、この結果の交換回数にも反映されています。

すでに整列した [1, 2, 3, 4] では、最初の3回の比較で交換がなく停止します。期待値と実際の出力は ([1, 2, 3, 4], 3, 0) です。整列済みかどうかを事前に知る必要はありません。巡回中に交換の有無を記録することで、次の巡回が不要だと判定できます。

発展例題：小さい値が末尾にあるとき

[2, 3, 4, 1] では、1巡目の比較で1が左に1位置しか進まず、[2, 3, 1, 4] となります。2巡目は [2, 1, 3, 4]、3巡目は [1, 2, 3, 4] です。期待値と実行値は ([1, 2, 3, 4], 6, 3) です。大きい値は一巡中に何度も右へ動けますが、小さい値は交換された直後に比較位置が右へ進むので、同じ巡回ではさらに左へ移動できません。

この方式では、最後の巡回で交換があっても、残りが1枚ならそれ以上の比較はありません。確定部分の条件から、その1枚も含めて整列が完了します。逆に「最後に交換した位置より右は確定」といった別の最適化を使う場合は範囲の定義が変わるので、上の回数と混ぜてはいけません。

一巡で止める誤りを直す

誤った手順が、図3のように最初の巡回だけで処理を終了したとします。入力 [4, 1, 3, 2] から得る [1, 3, 2, 4] は右端の4こそ確定していますが、3と2の並びが逆です。期待する [1, 2, 3, 4] と食い違う最初の原因は、交換の記録ではなく、未確定部分を次に調べる処理がないことです。

図3の左側に残る逆順の組を見て、対象範囲を右から1位置ずつ縮める外側の反復を加えます。そのうえで、1巡中に交換がなかった場合だけ早期終了します。修正後に同じ入力を再実行すると ([1, 2, 3, 4], 6, 4) となり、正しい順序とカードの枚数を確認できます。さらに、すでに整列済みの入力でも再実行し、不要な巡回を行わないことを確かめます。

別の誤りとして、changed を外側の反復の前で1回だけ偽にする場合があります。初回に交換が起きると、後の巡回で交換がなくても真のままです。結果がたまたま整列しても、早期終了が働かず比較回数が増えます。巡回ごとに偽へ戻し、その巡回の交換だけを記録するよう修正します。例えば [2, 1, 3, 4] は正しくは2巡目に交換がなく、比較5回、交換1回で停止します。

練習問題

以下はすべて整数カードで、添字は0始まりです。本文の関数と同じく、左から右へ比較し、等値は交換しません。比較回数は隣接する値の比較回数、交換回数は実際の入替えの回数です。返す形は整列後のリスト、比較回数、交換回数の順です。

1. [6, 4, 5] の1巡目の各比較後のリストと、関数の返す組を求めてください。
2. [7, 8, 9, 10] の返す組と停止した理由を答えてください。
3. [9, 7, 7] の返す組を求め、等しい7の交換の有無を答えてください。
4. [] と [12] をそれぞれ入力したときの返す組を答えてください。
5. [5, 8, 6, 7] について、各巡回後のリストと返す組を求めてください。

練習の答えと照合

1. 6と4を交換して [4, 6, 5]、6と5を交換して [4, 5, 6] です。次の巡回で4と5を比較して交換せず止まります。答えは ([4, 5, 6], 3, 2) です。3枚の値は各1枚残り、順序も昇順です。

2. 最初の巡回で3回比較し、どの組も左が右以下です。交換がないため終了し、答えは ([7, 8, 9, 10], 3, 0) です。4枚を失わず、そのまま昇順に並んでいます。

3. 9が2枚の7と順に交換され、1巡後は [7, 7, 9] です。次に7と7を比較して交換せず終了します。答えは ([7, 7, 9], 3, 2) です。7は2枚残り、互いに交換されません。

4. どちらも隣接する組がありません。答えはそれぞれ ([], 0, 0) と ([12], 0, 0) です。空の列にカードを足したり、1枚を消したりせずに返します。

5. 1巡目は [5, 6, 7, 8]、2巡目も [5, 6, 7, 8] です。2巡目は交換がないため終了します。答えは ([5, 6, 7, 8], 5, 2) です。4枚の内容を保ち、隣の値の順序も満たします。

練習の5入力と空・1枚の両方について、同じPython 3.14.8の関数で実行した出力は、上記の各組と一致しました。別の方法として各入力を小さい順に書き出し、カードの個数を元の列と照合しています。回数は処理表に沿って別に数えました。

確認に残すこと

1巡で未確定部分の最大値が右端に確定します。 交換がない巡回の後は、残りも昇順なので終了できます。 等値を交換しなければ、同値の元の順序は保たれます。 比較位置、交換、確定範囲、停止条件を別々に記録します。

どこで手が止まったかを見る

途中の列が合わないときは、最初に食い違った比較の前に戻り、交換後のカードを次の比較に使っているか確かめます。個別指導では、学習者に比較する2つの添字と値を声に出してもらい、表の1行を自分で更新できるかを見ます。結果だけが合っていても、比較回数と交換回数を別に数えられるかを確認します。

一巡で全部が確定すると考えた場合は、末尾に小さい値を置いた列で追いかけます。交換なしの終了を説明しにくい場合は、隣接する各組の大小と、すでに確定した右側との境界を順に確認します。カードが移る向きと確定する位置を結びつけると、整列の手順は自分の言葉で説明できます。