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




ソートのアルゴリズム

2006.04.20 00:08  整列

様々なソートアルゴリズムが考案されてきましたが、用途やデータの特徴、またはプログラムで使うデータ構造などに応じて、それらを的確に選ばなくてはなりません。以下の表は、代表的なソートのアルゴリズムとそれらの効率・特徴を示しています。

アルゴリズムの名前 効率 安定性 特徴
選択ソート
(Selection Sort)
O(n2) × 単純で最も直感的だが、効率が悪い
バブルソート
(Bubble Sort)
O(n2) 単純だが効率が悪い
挿入ソート
(Insertion Sort)
O(n2) ぼぼ整列されているデータに対して効率的
マージソート
(Merge Sort)
O(nlonn) 外部の記憶領域が必要
ヒープソート
(Heap Sort)
O(nlonn) × ヒープのデータ構造を応用する
クイックソート
(Quick Sort)
O(nlonn) × ほぼ整列されているデータに対して効率的ではない


選択ソート、バブルソートはソートのアルゴリズムの導入に紹介されるくらいで、実践で(現場で)使うことはほんとんどありません。データの特徴や問題の仕様に合わせて適切なアルゴリズムを設計することが重要です。マージソートは安定で高速、しかも実装が比較的容易なのでおすすめです。クイックソートは、理論上最速と言われていますが、安定ではないので注意が必要です。

| コメント(0) | トラックバック(0) | ↑ページトップ |




安定なソート

2006.04.20 00:06  整列

アルゴリズムを設計、選ぶ際に重要なポイントとなるのがその効率ですが、整列のアルゴリズムに関しては、それが「安定なソート」であるかを考慮に入れなくてはなりません。安定なソートとは、キーの値が同じ要素が2つ以上あるデータセットにおいては、それらの要素をソート前とソート後で順番が変わらないようなソート方法です。以下の例を見てみましょう。


stableSort.gif


上の例は、同じデータを整列したもので、どちらの配列もデータが昇順に並べ替えられましたが、左が「安定なソート」、右が「安定でないソート」です。このデータには、2つの「3」があります。「緑の3」と「青の3」です。初期データは、「緑の3」→「青の3」の順番となっていますが、「安定なソート」ではこの順番が保たれています。一方、「安定でないソート」では、「青の3」→「緑の3」と順番が逆になっています。

このソートの安定性を考慮に入れなければ、思わぬ失敗をしてしまいます。




stableSortCards.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |




整列 ソート

2006.04.20 00:05  整列

整列されたデータは探索(検索)し易い、ということをすでに紹介しました。データの整列は、多くのアルゴリズムの基礎になります。たくさんのデータを、あるキーに従って昇順(小さい順)または降順(大きい順)に整列するためのアルゴリズムをいくつか記録したいと思います。

sort.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |