安定ソート（あんていソート、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より先に来ている。
- 元の生徒番号順が保持されていないため不安定ソートとなる。
安定でないソート法を用いる場合でも、整列したいデータに元のデータ列の順序を追加しておき、ソートする際にその情報を参照するようにすれば、安定ソートに変更できる。しかし、この方法は、O(n)の外部記憶領域が必要となるという欠点があり、内部ソートが必要な場合には使えない。
関連項目[編集]
