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

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

例1:学生番号順 成績データ
学生番号 生徒名 テスト成績
010 A子 419
011 B男 366
012 C美 402
013 D生 453
014 E上 419
015 F崎 402
例2:成績順 安定ソート
学生番号 生徒名 テスト成績
011 B男 366
012 C美 402
015 F崎 402
010 A子 419
014 E上 419
013 D生 453
例3:成績順 不安定ソート
学生番号 生徒名 テスト成績
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 までの連番を一時的に記憶するのだから、 の記憶容量を必要とする(必要となる一時変数の個数という意味では )。したがって内部ソートが必要な場合には使えない。

関連項目編集