選択ソートは安定していますか?
1. 序章
このチュートリアルでは、 もしも 選択ソート 安定または不安定なアルゴリズムです.
2. 安定ソートアルゴリズム
ソートアルゴリズムは、等しい要素の相対的な順序を維持する場合、stableです。
たとえば、並べ替えるarrayとします。 の場合、安定したアルゴリズムにより、ソートされた出力のアイテムの前にアイテムが配置されます。
2.1. 例
単語配列を並べ替えたいとしましょう。
青と赤の2つの等しい要素が含まれています。 安定した並べ替えアルゴリズムは、入力配列での順序であるため、並べ替えられた出力で赤の前に青を配置します。
選択ソートはそれを行いますか? それは安定したまたは不安定なソートアルゴリズムですか?
3. 標準の選択ソートは安定していません
選択ソートの通常の定式化の擬似コードは次のとおりです。
の最小要素を位置に繰り返し配置し、の最小要素を要素と交換します。 その結果、は、最小のと交換したときに、等しい要素の後に配置される可能性があります。
3.1. 例
選択ソートが動物の配列をどのように処理するかを示しましょう。
外側のfor-loopの最初の反復で、アルゴリズムはそれが最小要素であると判断し、それを青と交換します。
次に、赤が配列の残りの部分()の最小項目であることを検出し、それを:と交換します。
最後に、通常の辞書式順序であるため、選択ソートは赤を:と交換します。
ご覧のとおり、これは2つの文字列の相対的な順序を維持しません。 それらは等しいので、最初に他の前にあったものが出力配列の最初に来るはずです。 ただし、選択ソートでは、最初の相対的な順序が逆であっても、赤が青の前に配置されます。
したがって、選択ソートの標準的な定式化は安定していないと結論付けることができます。
4. 選択ソートの安定したバリアントを作成できますか?
外側のループの-番目の反復で最小値をwithに交換する代わりに、最小値をから削除してとの間に挿入し、ソートされていないアイテムを効果的に1つ右にシフトすることができます。 このように変更すると、要素は並べ替えられた配列内でとるべき位置にのみ配置され、他の並べ替えられていないアイテムの相対的な順序には影響しません。
4.1. 例
例を考えてみましょう。 この新しいアルゴリズムが配列を上から並べ替える方法は次のとおりです。
予想どおり、青と赤の相対的な順序は変わりません。
4.2. 擬似コード
擬似コードは次のとおりです。
4.3. これは選択ソートですか?
問題は、挿入とシフトが選択ソートの標準的な定式化には存在せず、交換のみが存在することです。 したがって、今説明したアルゴリズムはSelectionSortの変形ではないと言えます。
しかし、そうだと主張する根拠もあります。 選択ソートの主な考え方を維持します。ソートされていない部分の最小要素を繰り返し選択し、それらを最後に配置することで、配列の最初にソートされたサブ配列を拡張します。ソートされたサブ配列の。 その観点からすると、挿入とシフトは実装の詳細にすぎません。 したがって、これらはロジックを変更しないため、アルゴリズムはSelectionSortの正当な変形です。
4.4. 安定した選択ソートとリンクリスト
このシフト選択ソートの問題は、安定しているものの、多くのシフトを実行することです。最悪の場合、最小要素は常に最後の位置()になります。配列は入力で増加せずにソートされます。 その場合、各外部ループの反復でシフトが発生し、合計でシフトが発生します。
これにより、時間計算量が標準の定式化と比較して悪化することはありません。 しかし、それは計算上の負担を追加し、実際にはアルゴリズムの効率を低下させます。
解決策は、配列をリンクリストに変換することです。その場合、要素をシフトする必要はありません。 私たちがする必要がある唯一のことは、へのポインタとへのポインタをリダイレクトすることです。
5. 結論
この記事では、選択ソートの安定性について説明しました。 アレイに適用すると、その標準的な定式化は不安定になります。 ただし、配列入力とリンクリスト入力の両方で安定するように変更できます。