安定なソート

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





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

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