
基本的な整列と安定性
用語の意味
選択ソートは未整列部分から最小値を選び、所定の位置に移します。挿入ソートは整列済みの部分の適切な位置に次の値を挿入します。バブルソートは隣り合う要素を比較して必要に応じ交換します。
使いどころと問題の見方
安定な整列では、比較に使うキーが等しい要素の元の順序が保たれます。受付順に並んだ申請を優先度で安定に整列すると、同じ優先度の中では受付順が保たれます。安定性は同じ値をどう扱うかも含め、具体的な実装で判断します。
確認問題【オリジナル】
受付順がA、B、Cで、優先度が順に2、1、2です。優先度を昇順に安定に整列するとどうなりますか。
ア.C、A、B
イ.B、A、C
ウ.B、C、A
エ.A、C、B
正解と理由
正解はイです。優先度1のBが先頭に来ます。AとCは優先度が等しいので、受付順のA、Cを維持します。