fc2ブログ



安定なソート

2006.04.20 00:06  整列

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


stableSort.gif


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

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




stableSortCards.gif

スポンサーサイト



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

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

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

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

↑ページトップ