安定ソートとはどういう概念なのか

安定ソートに関して、まとめます。

安定ソートとそうでないソートの例

wikipediaの例を参考にして、まとめます。
学生番号とテストの合計点が書かれたデータがあるとします。

学生番号	テスト合計点
1	419
2	366
3	402
4	453
5	419
6	402

このデータは、学生番号順に並んでいます。
これをテスト合計点順にバブルソートと選択ソートを使って並び替えてみたいと思います。

テスト合計点順にバブルソートで並び替えた場合

バブルソートで並び替えた場合以下のようになります。 計算過程は省略します。

学生番号	テスト合計点
2	366
3	402
6	402
1	419
5	419
4	453

同じ合計点の例に着目すると、学生番号順にならんでいることがわかります。
この性質のことを安定ソートといいます。
バブルソートは同じ点数の際は入れ替えないため、学生番号の順序も変わらないんですね。

テスト合計点順に選択ソートで並び替えた場合

テスト合計順に選択ソートを使って、並び替えてみたいと思います。

1.まずデータの中から最小得点のデータを探し出します。

学生番号2、点数366が最小なので、左端のデータと交換します。

　　　　

学生番号	テスト合計点
2	366
1	419
3	402
4	453
5	419
6	402

2.
一番目が決まったので、2番目から最小値を探索していきます。
最小値は402学生番号は3のデータになります。

　　　　

学生番号	テスト合計点
2	366
3	402
1	419
4	453
5	419
6	402

3.
3番目から最小値を探します。
最小値は402学生番号は6のデータになります。

　　　　

学生番号	テスト合計点
2	366
3	402
6	402
4	453
5	419
1	419

この時点で、419点において、学生番号が入れ替わってしまいました。

計算過程は省略しますが、学生番号が入れ替わったまま、得点順に並び替えられるのは、
選択ソートの性質上明らかですね。

このように元の順序が変わってしまうソートを不安定ソートといいます。