概要
概要
まず例で見る
安定ソートってなに
80 点の A さんと、80 点の B さんがいるとします。
点数順に並べ替えたあとも A さんが B さんより前のままなら、それは安定ソートです。
逆に、同じ 80 点なのに B さんが前へ出てしまうなら、不安定です。
つまり安定ソートは、『同じ値どうしの元の順番を残せるか』を見る言葉です。
同じ値の順番が残る
同じ値の順番が入れ替わることがある
同点や同じ値に意味がある並べ替え
概念 / 安定ソートとは
同じ点の A さんと B さんがいたとき、並べ替えたあとも A さんが前のまま残るなら安定ソートです。元の順番を保つかどうかを見る言葉です。
目次
このページでわかること
概要
まず例で見る
80 点の A さんと、80 点の B さんがいるとします。
点数順に並べ替えたあとも A さんが B さんより前のままなら、それは安定ソートです。
逆に、同じ 80 点なのに B さんが前へ出てしまうなら、不安定です。
つまり安定ソートは、『同じ値どうしの元の順番を残せるか』を見る言葉です。
同じ値の順番が残る
同じ値の順番が入れ替わることがある
同点や同じ値に意味がある並べ替え
考え方
同じ値を A, B のように区別して並べる
ソート後も A と B の順が残るか見る
同点や同じ値に意味がある場面を考える要点
用語の意味
同点や同じ値がある並べ替え
Bubble / Insertion / Merge
Selection / Heap / Quick の一般実装
補足
たとえば学年順に並べたあと点数順に並べても、同点の中では学年順を残せます。
同じ値に A と B のようなラベルを付けると違いが見えます。
安定かどうかは、速さではなく『同じ値の順番が残るか』を見る言葉です。
動きで確認
ここでは「同じ点数でも前後が変わらないかを見る」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。