1. 序章


このチュートリアルでは、 Straight SelectionSortで比較の数を決定します。


2. 問題文








整数、浮動小数点数、文字列、またはより複雑なオブジェクトなど、任意のタイプの要素を含む入力配列があります。 私たちの目標は、StraightSelectionSortアルゴリズムが入力配列を非減少的にソートするために行う比較の数を決定することです。 結果は、増加しない注文にも当てはまります。


2.1. ストレート選択ソート


ストレート選択ソートは、の先頭にソートされたサブ配列を繰り返し拡張します。 -番目のパスオーバーでは、の最小要素を選択し、の-番目の位置に配置します。 繰り返し、Straight Selection Sortは最小要素のインデックスを記憶し、-番目のパスの終わりにそれを交換します。


擬似コードは次のとおりです。






交換の数は、外部ループの反復ごとに1つのスワップのみが発生するためです。 比較の数はどうなりますか？


3. 比較数の計算式


外側のループの最初の反復では、他の要素とのみ比較されません。 それぞれについて、1つの比較があります。 したがって、アルゴリズムは最初の反復で合計で比較を行います。


同様に、2番目の外側の反復、3番目の反復、というように、-番目のパスまで比較を行います。 配列には要素があるため、比較できる要素はありません。 したがって、最後の反復では比較はありません。


そこから、 Straight Selection Sortsが外側のループ（）の-番目の反復で比較を実行することがわかります。 その結果、比較の総数は次のようになります。


 (1)    


入力配列については何も想定していなかったため、この式はその構造に関係なく保持されます。すでに並べ替えられている場合でも、StraightSelectionSortは比較を実行します。


これが、アルゴリズムが2次時間計算量である理由です。 スワップの数はですが、比較により、ストレート選択ソートは2次式になります。


4. 結論


この記事では、ストレート選択ソートでの比較数を計算しました。 入力配列に要素がある場合、アルゴリズムは配列がどのようなものであっても比較を実行します。