安定ソートのソースを表示

'''安定ソート'''（あんていソート、stable sort）とは、[[ソート]]（並び替え）の[[アルゴリズム]]のうち、同等な[[データ構造|データ]]のソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。

たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。

安定でないソート法を用いる場合でも、整列したいデータに元のデータ列の順序を追加しておき、ソートする際にその情報を参照するようにすれば、安定ソートに変更できる。しかし、この方法は、[[ランダウの記号|O]](n)の[[メモリ|外部記憶領域]]が必要となるという欠点があり、内部ソートが必要な場合には使えない。

== 関連項目 ==
*[[基数ソート]]（ラディックスソート）
*[[逆写像ソート]]
*[[シェーカーソート]]
*[[挿入ソート]]
*[[バケットソート]]
*[[バブルソート]]
*[[マージソート]]

[[Category:ソート|あんていそおと]]