先頭へ戻る

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

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

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

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

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

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

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

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

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


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー