高校情報I 選択ソート—未整列の範囲から最小の位置を選び確定部分を広げる｜武蔵野個別指導塾

資材の長さを並べ替え、最小位置の更新と交換回数から成立を読み解く選択ソートです。

よくあるのは、資材の長さを短い順に並べる際、最小値を見つけるたびに交換してしまう場面です。途中で交換しても昇順にできる処理はありますが、交換の回数や途中の配列は、ここで設計する選択ソートと一致しません。まず最後まで最小の位置を探し、それから交換する順序を追います。

何を答える問題か

選択ソートでは、未整列の範囲から最小の要素を選び、その範囲の先頭へ移します。出題の形には、各巡回後の配列を答えるもの、比較や交換の回数を数えるもの、途中の処理を直して正しく動く理由を説明するものがあります。いずれも、最小値とその位置を別々に記録することが手がかりです。

以下では整数のリストを短い順、つまり昇順に並べます。添字は0から始まり、長さを表す数は添字に含みません。空リストと要素1個も受け付け、同じ値は元の順序を保証しません。値どうしの大小比較を1回と数え、添字どうしの比較は数えません。異なる位置の要素を実際に入れ替えたときに交換1回とし、同じ位置のままの場合は0回です。

最小の位置を最後まで持ち歩く

添字iより前を確定部分、i以降を未整列部分とします。最初は確定部分が空です。未整列部分の先頭iを最小候補の位置mとし、その右側を順に調べます。今の候補より小さい値が現れたときにmをその位置へ更新し、同じ値なら更新しません。右端まで調べ終えてからiとmが違う場合に交換します。

図1のように、一巡中は候補の位置を更新するだけです。交換後は左端の要素が未整列部分の最小となり、確定部分が1個増えます。

図1の確定部分はすでに昇順で、そのどの値も未整列部分の値以下です。これが各巡回の前後に保たれる条件です。空の確定部分から始め、未整列部分の最小を末尾に加えるので、この条件は次の巡回でも保たれます。最後に残る1個はそれ以前の値以上ですから、全体が昇順です。

外側のiは0から要素数の2小さい位置まで進み、内側も右端で止まります。どちらも有限個の位置しか訪れないため停止します。空と1個の場合は外側の反復が0回で、そのまま昇順です。交換は値を増減させず位置を入れ替えるので、入力の要素の個数と内容も保たれます。

基本例題：資材を短い順に置く

長さを表すリスト [7, 3, 5, 2] を昇順にします。各巡回後のリストと、要素の比較回数、実際の交換回数を答えてください。最小候補と等しい値では候補を更新しません。答えは配列と整数の回数で表します。

手で調べると、最初は候補7に対し3、5、2を比較し、候補の位置は0、1、1、3と移ります。右端まで見てから7と2を交換します。次は残り [3, 5, 7] の最小3が先頭にあるため交換しません。最後は5と7を比較し、やはり交換しません。期待する配列は [2, 3, 5, 7]、比較は3回、2回、1回の計6回、交換は1回です。

図2のように、最初の巡回では候補の位置が変わっても、その時点で配列の値は動きません。選び終えた位置3と位置0を交換して初めて、先頭の2が確定します。

図2の先に続く2回の巡回でも、右側を最後まで調べることが比較回数に現れます。交換が不要でも比較は省略しません。

def selection_sort(values):
    a = values.copy()
    comparisons = 0
    swaps = 0
    for i in range(len(a) - 1):
        m = i
        for j in range(i + 1, len(a)):
            comparisons += 1
            if a[j] < a[m]:
                m = j
        if m != i:
            a[i], a[m] = a[m], a[i]
            swaps += 1
    return a, comparisons, swaps

print(selection_sort([7, 3, 5, 2]))

関数の入口でコピーを作るので、呼出し元のリストは変わりません。2つの回数を0に初期化し、外側のforで確定させる位置iを順に選びます。mにiを入れ、内側のforでiの右から末尾までの位置jを訪問します。比較の直前に回数を1増やし、値が小さいときだけmをjに替えます。

内側の反復が終わるとmは未整列部分の最小位置です。位置が異なる場合に同時代入で2つの値を入れ替え、交換回数を増やします。最後のreturnは完成した配列と2つの回数を返し、printがそれらを表示します。Python 3.14.8での実出力は ([2, 3, 5, 7], 6, 1) で、手で求めた期待値と一致しました。元の長さ2、3、5、7が各1個残り、順序も昇順です。

重複と交換の意味を調べる

標準例題では [4, 2, 4, 1, 2] を同じ規則で処理し、各巡回後の配列と回数を答えます。最初は位置3の1を選んで [1, 2, 4, 4, 2]、次は位置1の2を選ぶので交換なしです。3巡目は位置4の2を選んで [1, 2, 2, 4, 4]、4巡目は交換なしです。比較は4、3、2、1の合計10回、交換は2回です。Python 3.14.8で selection_sort([4, 2, 4, 1, 2]) を実行した結果も ([1, 2, 2, 4, 4], 10, 2) でした。入力の1が1個、2と4が各2個残ることも照合できます。

同じ値が候補より右に現れても、厳密に小さい場合だけ更新するため、その巡回では先に見つけた位置を選びます。ただし遠くの要素と交換すると、別の同値どうしの元の順序が逆になることがあります。たとえば長さが同じ2本を区別して [2番A, 2番B, 1] と置くと、先頭と末尾の交換後は [1, 2番B, 2番A] です。値は昇順でも、同じ長さの元の順序は保たれません。長さ以外の札の順序まで守る仕様なら、別の方法や追加の設計が必要です。

発展例題では、要素数が6のとき、この実装の比較回数を入力順によらず求めます。未整列部分の先頭と比べる相手は順に5、4、3、2、1個なので15回です。交換回数は入力に依存し、すでに昇順なら0回です。例えば [6, 5, 4, 3, 2, 1] では、最初の3巡でそれぞれ両端側の値を交換し、その後は交換せず3回です。実行結果は ([1, 2, 3, 4, 5, 6], 15, 3)、昇順入力では ([1, 2, 3, 4, 5, 6], 15, 0) でした。これは特定の実装で定めた回数であり、所要時間そのものではありません。

間違いの位置を表から直す

次の誤った処理は、小さい候補を見つけるたびに先頭と交換しています。入力 [7, 3, 5, 2] の最初の巡回では、7と3を交換した後、先頭の3と次の5を比べても交換しません。最後に先頭の3と2を交換します。この入力の最初の巡回後は [2, 7, 5, 3] です。正しい手順の [2, 3, 5, 7] と異なり、最終的に昇順でも、指定された途中状態や交換回数にはなりません。

図3のように、交換する場所が内側の反復の中にあることが原因です。候補位置だけを更新し、反復を抜けてから交換するように直します。

図3の修正後は、最初の巡回で位置1、次に位置3を候補にしてから1回だけ交換します。実際に誤った手順を有限回実行すると最初の巡回の交換は2回、修正後は1回でした。最終結果だけを見ず、最初に状態が食い違う箇所を比べると原因を特定できます。

失敗条件も仕様に入れます。上の関数は整数のリストを受け取る設計です。文字列と整数が混ざる入力では比較時にTypeErrorが起こり、整列結果は返りません。呼出し側は入力を検査し、異常を知らせて再入力を求める設計にできます。空リストは不正ではなく正常な入力で、比較と交換は0回です。時間切れや外部の道具の故障はこの関数の内部では発生させていません。外部から入力を受ける仕組みに組み込む場合は、途中の失敗を成功として表示せず、処理を中止して原因と再試行の可否を呼出し側に伝えます。

確かめるための5問

次の各問でも添字は0始まり、候補と同値なら更新せず、交換は異なる位置の入替えだけを数えます。答えは指定された配列、位置、整数または説明で表してください。

1. 展示用の板 [8, 6, 9] の最初の巡回後の配列と、候補の最終位置を答えてください。
2. 箱の幅 [5, 1, 4, 3] を最後まで整列した配列と、比較回数と交換回数を答えてください。
3. 棒の長さ [3, 3, 2] の最初の巡回で、同値を見た後の候補位置と、巡回後の配列を答えてください。
4. 入力 [] と [12] のそれぞれについて、返す配列、比較回数、交換回数を答えてください。
5. 部材 [10, 8, 6] の最初の巡回で、候補発見のたびに先頭と交換する誤りと正しい処理の巡回後の配列をそれぞれ答え、相違の原因を説明してください。

答えと照合

1. 最初の候補位置0の8より位置1の6が小さく、位置2の9は6より小さくありません。候補の最終位置は1、交換後は [6, 8, 9] です。3本の値がそのまま残り、先頭は最小の6です。
2. 各巡回後は [1, 5, 4, 3]、[1, 3, 4, 5]、[1, 3, 4, 5] です。答えは [1, 3, 4, 5]、比較6回、交換2回です。1、3、4、5が各1個あり、元の箱の幅を失っていません。
3. 位置1の3は候補の3と等しいため、候補位置は0のままです。位置2の2で候補を更新し、交換後は [2, 3, 3] です。長さ3が2本残り、先頭の2は入力中の最小です。
4. [] は ([], 0, 0)、[12] は ([12], 0, 0) です。比較相手がないため両方とも交換はありません。それぞれ入力の個数を保ち、昇順の条件を満たします。
5. 誤りは最初に10と8を、次に8と6を交換するので [6, 10, 8] です。正しくは位置2を選び、最後に10と6を交換して [6, 8, 10] です。誤りは候補の更新と交換を同じ時点で行うため、途中の並びと交換回数が変わります。どちらも元の3本を保ちますが、求められた巡回の規則に合うのは後者です。

Python 3.14.8で基本の関数に問1から問4の入力を渡した最終出力は、順に ([6, 8, 9], 3, 1)、([1, 3, 4, 5], 6, 2)、([2, 3, 3], 3, 1)、([], 0, 0) と ([12], 0, 0) でした。問1と問3は途中状態も手で追い、問5は1巡だけ実行して照合しました。数例が一致することと、前述の確定部分の条件による一般的な説明は別です。

失敗を含む実行確認

Python 3.14.8で、正常な入力 [7, 3, 5, 2]、[4, 2, 4, 1, 2]、[6, 5, 4, 3, 2, 1]、[]、[12] を実行し、期待した配列と回数に一致しました。昇順入力も交換0回を確認しました。手計算で小さい順に並べた結果と、入力の各値の個数を照らし合わせています。

失敗側も同じだけ具体的に確かめます。異なる型が混ざる [2, ‘x’] と [‘x’, 2] は、どちらも期待どおりTypeErrorでした。値がNoneの [2, None] もTypeError、リストの代わりにNoneを渡すとAttributeErrorです。数値を含む文字列 [ ‘3’, ‘12’ ] は文字列どうしなら比較できてしまうため、整数の仕様外と判定する必要があります。これらは例外の有無だけで正しい結果とみなさず、入力検査で拒否する対象です。時間切れと外部の道具の故障は関数本体の入力では再現できず、呼出し側の試験として別途、制限時間超過と読み込み失敗を模擬し、中止と再試行を確認する必要があります。

要点

• 未整列部分の最小位置を右端まで探します。
• 候補の更新と交換を分け、巡回後に交換します。
• 確定部分は昇順で、その値は残りの値以下です。
• 比較回数と実際の交換回数は別に数えます。
• 同値の元の順序は保証しません。

手が止まったときに見る場所

候補の値を書けても位置を追えないときは、各比較の前後にi、j、mと配列を並べてください。mが変わった行で配列も変えたなら、交換を行う位置を見直します。個別指導で確かめる際も、完成した配列だけでなく、最初の巡回の候補の変化を本人の言葉で説明できるかを見ると、処理のずれを見つけやすくなります。

確定部分と残りの関係を言葉にできれば、選択ソートの各交換には理由が見えてきます。