安定ソート

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

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

例１：学生番号順　成績データ
学生番号	生徒名	テスト成績
010	A子	419
011	B男	366
012	C美	402
013	D生	453
014	E上	419
015	F崎	402

例２：成績順　安定ソート
学生番号	生徒名	テスト成績
011	B男	366
012	C美	402
015	F崎	402
010	A子	419
014	E上	419
013	D生	453

例３：成績順　不安定ソート
学生番号	生徒名	テスト成績
011	B男	366
015	F崎	402
012	C美	402
014	E上	419
010	A子	419
013	D生	453

生徒番号015が012の先に来ており、また014も010より先に来ている。
元の生徒番号順が保持されていないため不安定ソートとなる。

安定でないソート法を用いる場合でも、整列したいデータに元のデータ列の順序を追加しておき、ソートする際にその情報を参照するようにすれば、安定ソートに変更できる。形式的には、ソートしたい項目と元の順番を表す項目のペアを辞書式順序でソートする、ということである。この方法は（入力データ自体が元々順番を表す項目を含んでいるのでない限り）元の順番を表す情報を記憶する必要がある。すなわち、長さ n の入力に対し、0 から n-1 までの連番を一時的に記憶するのだから、 $O(n\log n)$ の記憶容量を必要とする（必要となる一時変数の個数という意味では $O(n)$ ）。したがって内部ソートが必要な場合には使えない。

関連項目[編集]