fc2ブログ



選択ソート セレクションソート Selection Sort

2006.04.20 00:13  整列

選択ソートは、ソートアルゴリズムの導入となる最も単純なアルゴリズムの1つです。最も思いつきやすく、直感的なアルゴリズムだと思います。

選択ソート
各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。
selectionSortStep2.gif
1.「未ソートの部分」から最小の要素を探します。
選択ソート
2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。
選択ソート
1. 2. を未ソートの部分がなくなるまで繰り返します。

選択ソート
1. 初期状態は全ての要素が未ソートの部分に属します。
2. 未ソートの部分から最小値2を選択し、未ソートの部分の先頭7と交換します。
3. 未ソートの部分から最小値3を選択し、未ソートの部分の先頭5と交換します。
4. 未ソートの部分から最小値5を選択し、未ソートの部分の先頭11と交換します。
5. 未ソートの部分から最小値6を選択し、未ソートの部分の先頭8と交換します。
6. 未ソートの部分から最小値7を選択し、未ソートの部分の先頭12と交換します。
7. 未ソートの部分から最小値8を選択し、未ソートの部分の先頭11と交換します。
8. 未ソートの部分から最小値11を選択し、未ソートの部分の先頭12と交換します。
9. ソートが完了します。


選択ソートインデックス

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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ