安定ソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/05 04:42 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2022年5月） |
安定ソート（あんていソート、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 までの連番を一時的に記憶するのだから、 の記憶容量を必要とする（必要となる一時変数の個数という意味では ）。したがって内部ソートが必要な場合には使えない。
関連項目
安定ソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/10 08:33 UTC 版)
詳細は「安定ソート」を参照 同じ値に関して、ソート前の順序がソート後も維持されているソートを安定ソートという。 安定ソートでないソートであっても、ソート条件に元の順序を含めることで必ず安定ソートにすることが可能である。しかしながら、別途元の順序を記憶する領域が必要になることから、内部ソートであっても外部ソートになってしまう。（→#内部ソートと外部ソート）
※この「安定ソート」の解説は、「ソート」の解説の一部です。
「安定ソート」を含む「ソート」の記事については、「ソート」の概要を参照ください。
安定ソートと同じ種類の言葉
- 安定ソートのページへのリンク
