[解決済み] 選択ソートが安定する理由と不安定な理由

質問

私は、以下のことを知っています。 selection sort は、安定または不安定として実装することができます。しかし、それはどのように実現されるのでしょうか。ソートアルゴリズムは安定か不安定しか選べないと思うのですが。誰か説明してください。

どのように解決するのですか？

基本的に selection sort このため、各ラウンドの最後に発生するスワップによって、同じ値を持つアイテムの相対的な順序を変更することができます。

例えば、次のようにソートしたとします。 4 2 3 4 1 で selection sort .

最初のquot;round"は、各要素を通過して最小の要素を探します。そして、1が最小の要素であることを発見します。 1 2 3 4 4

元のリストの最初の 4 は、他の 4 の後のスポットに移動しました。

安定した状態とは、次のようなものであることを思い出してください。

同じ値を持つ要素の相対的な順序が維持されること。

さて。 selection sort で動作します。 一連の値の中から「最小」の値を見つけ、それを最初の値と入れ替える。 :

コード

2, 3, 1, 1 # 0からnまでスキャンして「最小」の値を探す

1, 3, 2, 1 # '最小'と要素0を入れ替える.

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

1, 1, 2, 3 # '最小'と要素1を入れ替える。

...といった具合に、並べ替えが完了するまで続けます。

これを安定させるために、値を入れ替える代わりに、「最小」の値を挿入します。 :

コード

2, 3, 1, 1 # 0からnまでスキャンして「最小」の値を探す

1, 2, 3, 1 # pos 0 に「最低」を挿入し、他の要素を後ろに押しやる。

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

1, 1, 2, 3 # pos 1 に '最小' を挿入し、他の要素を後ろに押しやる。

...といった具合に、並べ替えが完了するまで続けます。

不安定な選択ソートアルゴリズムを安定になるように修正するのは、それほど難しいことではないはずです。