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

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

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

{| class="wikitable"
|+ 例１：学生番号順　成績データ
! 学生番号 !! 生徒名 !! テスト成績 
|-
! 010
| A子 || 419 
|-
! 011
| B男 || 366 
|-
! 012
| C美 || 402 
|-
! 013
| D生 || 453 
|-
! 014
| E上 || 419 
|-
! 015
| F崎 || 402 
|}

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

{| class="wikitable"
|+ 例３：成績順　不安定ソート
! 学生番号 !! 生徒名 !! テスト成績 
|-
! 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 までの連番を一時的に記憶するのだから、<math>O(n \log n)</math> の記憶容量を必要とする（必要となる一時変数の個数という意味では <math>O(n)</math>）。したがって[[内部ソート]]が必要な場合には使えない。

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

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