Pythonの選択ソート(selection sort)
このレッスンでは、最小の要素を探しては正しい位置に置く操作を繰り返して、選択ソートを実装します。
はじめに
どんな問題を解決するか
並べ替えアルゴリズムの中には、要素を動かす回数をできるだけ少なくしようとするものがあります。要素を動かすのに手間がかかる場合には、これが大事になります。選択ソートは、バブルソートとは違う作戦をとります。先に正しい要素を見つけてから、1回だけ動かすのです。
身近なたとえ
選択ソートは、背の順にチームのメンバーを選んでいくようなものです。まだ待っている全員を見渡して、いちばん背の低い人を呼び、列の次の場所に立たせます。続いて残りの人の中から次に背の低い人を探し、誰もいなくなるまで続けます。
for start in range(len(result)):📍 列の次の空いた場所minimum = start🤔 この人がいちばん背が低いと仮定するresult[index] < result[minimum]🔎 残りからもっと背の低い人を探すresult[start], result[minimum] = ...🔄 いちばん背の低い人を空いた場所へ選択ソートは、まだ整列していない部分から最小の要素を見つけ、ソート済みの部分のすぐ次の位置にある要素と入れ替えることを繰り返します。比較は O(n²) 回必要ですが、入れ替えは最大でも n - 1 回です。
重要なポイント
startより左はすでにソート済みで、startから先はまだ並べ替えていません。minimumは、まだ整列していない部分でこれまでに見つけた最小値の位置を覚えておきます。- 内側のループ
for index in range(start + 1, len(result)):は残りのリストを調べます。 result[start], result[minimum] = result[minimum], result[start]で、1つの位置につき1回だけ入れ替えます。
どんな場面で使う?
- 並べ替えの戦略を学んで比べる。
- 要素の書き込みや移動には時間がかかり、比較は軽く済む場面。
- k 回目で止めて、小さいほうから k 個の要素を取り出す。
使わなくてよいとき
- 実際のプログラム:
sorted()のほうがずっと速いです。 - ほぼソート済みのデータ:選択ソートはそれでも全部を調べますが、挿入ソートならすぐに終わります。
Pythonの選択ソート(selection sort)のビジュアライザー
O(n²)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
実行結果
[11, 12, 22, 25, 64]
コードの解説
変数minimumは、残りの部分で最小の値がある位置を記録します。各走査の最後に、その値を位置startと入れ替えます。比較の回数が多いため計算量は常にO(n²)ですが、入れ替えは最大でもn回しか行いません。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
内側のループの中で入れ替える
入れ替えの回数が多く、遅くて分かりにくい並べ替えになってしまいます。
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
- 配列の最小値 リスト内の最小値を求めてください。 簡単
- K-th Smallest Element Find the k-th smallest value without fully sorting. 中級