選択ソート セレクションソート Selection Sort
2006.04.20 00:13 整列
選択ソートは、ソートアルゴリズムの導入となる最も単純なアルゴリズムの1つです。最も思いつきやすく、直感的なアルゴリズムだと思います。

Program は、データの数 size を読み込み、size個の整数を配列 data に読み込んで、配列の要素を選択ソートによって昇順に整列し、それを出力します。プログラムの本体である selectionSort を見てみましょう。07行目の最初の for ループによって、「未ソートの部分の最小値と先頭の要素を交換する処理」を繰り返します。Fig.に示すように、front は未ソートの部分の先頭の要素を指します。次の10行目のforループによって、未ソートの部分から最小値を見つけます。インデックスminIndexが最小値を示すように、minIndexを更新していきます。14-16で、最小値と先頭の要素を交換します。
選択ソートの計算量を考えてみましょう。データの数をnとすると、選択ソートは未ソートの部分の最小値を見つけるためにn-1回、n-2回、n-3回・・・1回の比較演算を行います。よって合計の比較演算の回数は(n2-n)/2となり、選択ソートはO(n2)のアルゴリズムとなります。
![]() |
各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。 |
![]() |
1.「未ソートの部分」から最小の要素を探します。 |
![]() |
2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。 |
![]() |
1. 2. を未ソートの部分がなくなるまで繰り返します。 |

Program は、データの数 size を読み込み、size個の整数を配列 data に読み込んで、配列の要素を選択ソートによって昇順に整列し、それを出力します。プログラムの本体である selectionSort を見てみましょう。07行目の最初の for ループによって、「未ソートの部分の最小値と先頭の要素を交換する処理」を繰り返します。Fig.に示すように、front は未ソートの部分の先頭の要素を指します。次の10行目のforループによって、未ソートの部分から最小値を見つけます。インデックスminIndexが最小値を示すように、minIndexを更新していきます。14-16で、最小値と先頭の要素を交換します。
選択ソートの計算量を考えてみましょう。データの数をnとすると、選択ソートは未ソートの部分の最小値を見つけるためにn-1回、n-2回、n-3回・・・1回の比較演算を行います。よって合計の比較演算の回数は(n2-n)/2となり、選択ソートはO(n2)のアルゴリズムとなります。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |