0

一連のインターネット トランザクションに適用される選択と挿入の並べ替えの安定性に関する例を見てきました。

ここに画像の説明を入力

そして、場所の基準を使用して選択ソートを使用してソートしようとするパスを1つ作成しました。

ここに画像の説明を入力

私が知っていることは、選択ソートが順序付けられていない部分の右セクションの要素のインデックスを選択し、それを左セクションの前に配置することを意味します。最初のパスでは、シカゴ 09:00:00 が適切な位置にあり、これより短い時間のシカゴは他にありません。次に、Phoenix 09:00:03 に渡すので、右側の部分 (シカゴ 09:00:59) で小さい要素をチェックします。この要素は小さいため、最終的には次のようになります。

Chicago 09:00:00
Chicago 09:00:59

ただし、例では、選択ソートを使用したため不安定であり、挿入ソートを使用すると安定する可能性があると述べています

比較で何が間違っていますか？

また、この例を置く別の例をここに見ました：

Sort this elements
(4,0)(4,1)(1,0)

選択ソートを使用し、各タプルの最初の要素のみをチェックすると、次のようになります。

(1,0)(4,1)(4,0)

安定していないようですが、挿入ソートを使用すると、次のようになります。

(1,0)(4,0)(4,1)

ただし、元の配列にわずかな変更を加えた場合:

(4,1)(4,0)(1,0)

最初の要素のみを比較すると、最終的に次のようになるため、挿入ソートも安定しません。

(1,0)(4,1)(4,0)

わかりました。両方の要素を比較する場合、選択ソートも安定する可能性があります。これらの証明の何が問題なのですか?

4

1 に答える 1

1

最後の例では、挿入ソートは安定しています。ソート アルゴリズムの安定性とは、同じキーを持つアイテムが相互に同じ順序を維持することを意味します。

したがって、最後の例では次のようになります。

(4,1)(4,0)(1,0)

挿入ソートの結果は次のようになります。

(1,0)(4,1)(4,0)

項目(4,1)と(4,0)は、互いに対して同じ順序を維持しています。つまり、元の配列で(4,1)前に来(4,0)て、最終的な配列でその項目の前にあるということです。ソートは安定しています。

また、選択ソートを使用して特定の配列をソートした結果は、選択ソートが安定していることを示している場合があります。つまり、選択の並べ替えが等しいアイテムの相対的な順序を変更するという保証はありません。たとえば、次のように開始します。

(4,1)(1,0)(4,0)

選択ソートが生成します

(1,0)(4,1)(4,0)

その場合、選択ソートは と の相対順序を変更しませんでし(4,1)た(4,0)。しかし、それは選択ソートが安定していることを意味しません。止まった時計でも一日二回は正しい。

于 2013-09-22T14:57:51.760 に答える