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

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


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

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