安定ソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2009年10月14日 (水) 21:13時点における218.45.177.50 (トーク)による版 (この文は不要でしょう。)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

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

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

安定でないソート法を用いる場合でも、整列したいデータに元のデータ列の順序を追加しておき、ソートする際にその情報を参照するようにすれば、安定ソートに変更できる。しかし、この方法は、O(n)の外部記憶領域が必要となるという欠点があり、内部ソートが必要な場合には使えない。

関連項目