バブルソートと挿入ソートが安定で、選択ソートが安定でない理由

安定・不安定とは

まず、安定であるとは、ソート処理をしても同じ値の順番が変化しないことを意味し、不安定であるとはソート処理をすると同じ値の順番が変化することを意味する。

バブルソート

まず、バブルソートが安定であることを示す。
例えば[9,3,9,2]という配列があるとする。・・・①
そこで、9が2つあるため、1番最初の9をa、3番目の9をbとする。
ここで、バブルソートが動作すると、
0回目[a,3,b,2]
1回目[a,3,2,b]
2回目[a,2,3,b]
3回目[2,a,3,b]
4回目[2,3,a,b]
となる。このように、元の配列（①）からa,bという順番である必要がある。そこで上記で示した例でも[2,3,a,b]というように元の順番であるa,bに従っているため、安定しているとえる。

挿入ソート

次に、挿入ソートについて考える。今回も[9,3,9,2]という配列を例として用いる。
そこで、1番最初の9をa、3番目の9をbとする。
0回目[a,3,b,2]　ここではaを整列済みとする。
1回目[3,a,b,2]　この処理で[3,a]が整列済みとなった。
2回目[3,a,b,2]　この処理で[3,a,b]が整列済みとなった。
3回目[2,3,a,b]
このように、元の配列（①）からa,bという順番である必要がある。そこで上記で示した例でも[2,3,a,b]というように元の順番であるa,bに従っているため、安定しているとえる。

選択ソート

最後に選択ソートについて考える。
今回も[9,3,9,2]という配列を例として用いる。
そこで、一番最初の9をa、一番最後の9をbとする。
ここで、選択ソートが動作すると
0回目[a,3,b,2]
1回目[2,3,b,a]
ここでソートは完了する。元の順番ではa,bであったはずだが、選択ソート処理により、b,aの順番となってしまい、元の順番であるa,bと変化している。このため、選択ソートは不安定と言える。