BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
選択ソート
残りの最小値を選ぶ
選択ソートは、未整列の部分から最小値などを選び、順に確定位置へ移す整列方法です。昇順なら、最初に全体の最小値を先頭へ、次に残りの最小値を二番目へ置きます。毎回、未処理の範囲から一つの値を選ぶ点が特徴です。隣同士を繰り返し交換するバブルソートとは動作が異なります。
Pythonによる例
def selection_sort(values):
result = list(values)
for start in range(len(result) - 1):
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
内側のループでは最小値の位置を覚え、調べ終えてから交換します。
手順の例
5、2、4、1なら、最初に1を見つけて5と交換し、1、2、4、5になります。次は先頭の1を除く範囲で最小値を選びます。一回の選択で一つの確定位置が増えますが、途中の未整列部分が偶然整って見えることもあります。手順を省略せず、問題が指定する回数を確認します。
比較回数と交換回数
未処理の範囲を毎回調べるため、標準的な比較回数はn(n-1)/2程度で、時間計算量はO(n²)です。一方、交換は各段階で多くても一回なのでO(n)です。比較と交換の費用が異なる場面では、この違いが評価に関係します。既に整列済みでも、同じように最小値を調べる実装なら比較は減りません。
安定性と試験
離れた位置の要素を交換すると、同じキーを持つ要素の相対順序が変わる場合があります。したがって典型的な交換方式は安定とは限りません。試験では「最小値を探してから交換」という段階を区別し、内側の比較のたびに交換する別の実装と混同しないようにします。要素の値だけでなく同じ値の識別番号も付けると、安定性を確認しやすくなります。
参考資料
内容確認日:2026-11-13
この用語に関連する問題
1問用語一覧
6件ゼロトラスト
所在地だけで信頼を決めない ゼロトラストは、社内ネットワークにいるという理由だけで暗黙に信頼せず、資源へのアクセスをその都度の条件に基づいて判断する考...
成長マトリクス
アンゾフの成長マトリクスとして知られ、商品・サービスの成長の種類を大きく4つの分類に分けたものを指す。 既存製品・既存市場:市場浸透 既存製品・新規市場...
生産者危険
商品を製造する際、商品に異常がないか調べるためにロット毎に検査をすることが多くあります。 その際、ロットすべて検査するわけにいかないので、一部取り出し...
線形探索
一つずつ確かめる探索 線形探索は、配列やリストの要素を順に調べ、目的の値と一致するものを探す方法です。逐次探索とも呼びます。データが整列されていなくて...
製品ライフサイクル
一つの製品が、開発され市場に投入された時から、販売を終了するまでの流れを現したもの。分析対象となる商品・サービスが現状どこに位置づけされるかを見極め、...
選択ソート
残りの最小値を選ぶ 選択ソートは、未整列の部分から最小値などを選び、順に確定位置へ移す整列方法です。昇順なら、最初に全体の最小値を先頭へ、次に残りの最...