安定ソートとソートの安定性とは？

安定ソートとソートの安定性の意味

整列前に等しい値を持っていた要素同士の、整列後の相対的な並び順が保たれる性質を「安定」という。挿入ソートやマージソート、バブルソートは安定ソートだが、クイックソートや選択ソートの一般的な実装は不安定になりやすい。

安定ソートとソートの安定性の具体例

「名前」で既に整列済みの名簿を「学年」で安定ソートすると、同じ学年内では元の名前順が保たれたまま並び替わる。

安定ソートとソートの安定性は試験でどう引っ掛けられる？

安定は「等しい値の要素の元の並び順が保たれる」性質であって、速さとは無関係。安定＝高速と思い込まない。挿入・バブル・マージソートは安定、クイックソート・選択ソート・ヒープソートは一般に不安定と対で覚える。

安定ソートとソートの安定性と関連する用語

• 整列アルゴリズム（バブルソート・選択ソート・挿入ソート）
• クイックソート・マージソート・ヒープソート