RSS
ソートのアルゴリズムのうち、データ列の中に、ソート後の順位が同じになるデータが複数あるとき、ソート後にソート前の位置関係が崩れない保証があるもののことです。
たとえば、ソートする対象のデータが、「名前」と「年齢」で構成されており、以下の順番で並んでいるとします。
このデータ列を、年齢の昇順にソートしたいとします。データ列には、26歳の人が２人含まれているため、この２人の位置関係が崩れない（つまり、Aさんが Dさんより手前側に位置する）ことが保証されていれば、安定ソートであるといえます。安定ソートであれば、ソート結果は必ず次の並びになります。
ここで、Aさんと Dさんの位置が反対になる可能性があるソートアルゴリズムは、「安定ソートではない」「安定でない」といったふうに表現されます。
代表的な安定ソートに、マージソート、バブルソート、挿入ソートなどがあります。
マージソートの解説がアルゴリズムとデータ構造編【整列】第７章に、バブルソートが第３章、挿入ソートが第４章にあります。
安定ソートでないソートアルゴリズムでも、順序に関する情報を追加情報として、安定ソートに仕立てることは可能ですが、その分だけ余計なメモリ領域が必要になってしまいます。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |