Stability

このレッスンでは、バブルソートアルゴリズムの安定性について確認します。

安定性とは何でしょうか？

ソートアルゴリズムが安定であるとは、同じキーを持つ2つのオブジェクトが、ソート前の入力配列と同じ順序でソート後の出力に現れることを言います。

例えば、配列 [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] をソートする場合を考えます。ここには 8₁ と 8₂ で表される2つの「8」があります。ソート後、2つの可能性のある配列が得られます。 [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] と [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] です。これら両方の配列はソートされていますが、2番目の配列では2つの「8」の順序が入れ替わっています。一方、最初の配列では入力配列と同じ順序になっています。

それでは、バブルソートアルゴリズムでこれを確認してみましょう。

1回目のパス: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

2回目のパス: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

すべてのパスが終了した後、最終的な出力は次のようになります: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

出力配列と入力配列の両方で、「8」の順序が同じであることに注目してください。

したがって、バブルソートアルゴリズムは安定的です！