安定ソート | Programming Place Plus　用語集

名称

ソートのアルゴリズムのうち、データ列の中に、ソート後の順位が同じになるデータが複数あるとき、ソート後にソート前の位置関係が崩れない保証があるもののことです。

たとえば、ソートする対象のデータが、「名前」と「年齢」で構成されており、以下の順番で並んでいるとします。

このデータ列を、年齢の昇順にソートしたいとします。データ列には、26歳の人が２人含まれているため、この２人の位置関係が崩れない（つまり、Aさんが Dさんより手前側に位置する）ことが保証されていれば、安定ソートであるといえます。安定ソートであれば、ソート結果は必ず次の並びになります。

ここで、Aさんと Dさんの位置が反対になる可能性があるソートアルゴリズムは、「安定ソートではない」「安定でない」といったふうに表現されます。

代表的な安定ソートに、マージソート、バブルソート、挿入ソートなどがあります。

マージソートの解説がアルゴリズムとデータ構造編【整列】第７章に、バブルソートが第３章、挿入ソートが第４章にあります。

安定ソートでないソートアルゴリズムでも、順序に関する情報を追加情報として、安定ソートに仕立てることは可能ですが、その分だけ余計なメモリ領域が必要になってしまいます。