arrays - 計算量 - 選択ソート 降順




選択ソートが安定または不安定になる可能性がある理由 (3)

私はselection sortが安定したものとしても不安定なものとしても実装できることを知っていselection sort 。 しかし、私はそれがどのようになり得るのだろうか。 ソートアルゴリズムは安定している場合もあれば、不安定な場合もあります。 誰かが説明できますか?


この配列があるとしましょう。

A = {3, 3, 1}

位置0から開始して、選択ソートは最小値を検索し、現在の要素を最小値と交換します。 A場合、最初の31を入れ替え、2番目のステップでは何もしません。

最初の3が2番目の前に来るはずだったので、これは安定していません。 配列の代わりにリンクリストを使用し、スワップする代わりに正しい位置に要素を挿入すると、選択ソートは安定します。


ソートルーティングが選択ソートであるという事実は、それに関するすべてを定義するわけではありません。 異なる実装では異なる方法で行うことができる決定がまだあり、異なる選択は安定したまたは不安定なソートのどちらかを生成するかもしれません。 (ほとんどの種類の安定したものは、必ずしもそうである必要はありません。通常、興味深い理論的な問題は、その種類安定して実装できるかどうかです。)


基本的にselection sortでは、各「ラウンド」の終わりに行われるスワップは同じ値を持つ項目の相対的な順序を変えることができます。

たとえば、 4 2 3 4 1selection sort

最初の「ラウンド」は各要素を通過して最小の要素を探します。 1が最小要素であることがわかります。 それから1を最初の場所に入れ替えます。 これにより、最初のスポットの4が最後のスポットに入ります1 2 3 4 4

4の相対的な順番が変わりました。 元のリストの「最初の」4は、他の4の後の場所に移動されています。

安定の定義を覚えている

同じ値を持つ要素の相対順序は維持されます。

selection sort は、一連の値の中で最小の値を見つけ、それを最初の値と交換することによって機能します

コード:

2、3、1、1#0からnまでをスキャンし、「最小」の値を見つける

1、3、2、1#要素0と 'least'を入れ替えます。

1、3、2、1#1からnまでをスキャンして「最小」の値を見つける

1、1、2、3#要素1と 'least'を入れ替えます。

...ソートされるまで続きます。

これを安定させるには、値を交換するのではなく、代わりに 'least'値を挿入します

コード:

2、3、1、1#0からnまでをスキャンし、「最小」の値を見つける

1、2、3、1#位置0に 'least'を挿入し、他の要素を押し戻します。

1、3、2、1#1からnまでをスキャンして「最小」の値を見つける

1、1、2、3#位置1に 'least'を挿入し、他の要素を後ろに押します。

...ソートされるまで続きます。

不安定になる選択ソートアルゴリズムを安定させるために修正することはそれほど難しくないはずです。





sorting