選択ソートとは？

詳細解説

選択ソートは、データ列の未整列の部分から最小値（降順なら最大値）を見つけ、それを未整列部分の先頭の要素と入れ替える、という操作を繰り返して整列するアルゴリズムです。1回の操作ごとに、先頭側の整列済みの範囲が1つずつ広がります。要素数をnとすると、最小値を探すための比較がおよそn(n−1)/2回必要で、計算量はデータの並びに関わらずO(n²)になります。要素の入れ替え回数は、多くてもn−1回と少ないのが特徴です。バブルソートが隣り合う要素の比較・交換を繰り返すのに対し、選択ソートは最小値を選んで1回で位置へ移す点が違います。処理は単純ですが、同じ値の順序が保たれない（安定でない）場合があります。シラバスでは、選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソートなどが用語例として挙げられています。

FE試験での出題ポイント

• 1最小値を選んで先頭と交換する手順を、途中経過で追えるようにする
• 2比較回数が常にn(n−1)/2程度で、計算量がO(n²)であることを説明できるようにする
• 3バブルソートとの動作の違いを区別できるようにする

関連用語