広告
選択ソートは、単純なソートアルゴリズムです。 このソートアルゴリズムは、リストを左端にソートされた部分と右端にソートされていない部分の二つの部分に分割するインプレース比較ベースのアルゴリズ 最初は、ソートされた部分は空であり、ソートされていない部分はリスト全体です。
ソートされていない配列から最小の要素が選択され、左端の要素と交換され、その要素がソートされた配列の一部になります。 このプロセスは、ソートされていない配列の境界を1つの要素だけ右に移動し続けます。
このアルゴリズムは、平均および最悪の場合の複雑さがΣ(n2)であり、nは項目数であるため、大きなデータセットには適していません。
選択ソートはどのように機能しますか？
以下に示す配列を例として考えてみましょう。
ソートされたリストの最初の位置については、リスト全体が順番にスキャンされます。 現在、14が格納されている最初の位置では、リスト全体を検索し、10が最も低い値であることがわかります。
だから、14を10に置き換えます。 リスト内の最小値である1回の反復10の後、ソートされたリストの最初の位置に表示されます。
33が存在する2番目の位置については、リストの残りの部分を線形にスキャンします。
14がリスト内で2番目に低い値であり、2番目の場所に表示されるはずです。 私たちはこれらの値を交換します。
二つの反復の後、二つの最小値がソートされた方法で先頭に配置されます。
同じプロセスが配列内の残りの項目に適用されます。
以下は、ソートプロセス全体の絵の描写です−
さて、私たちは選択ソートのいくつかのプログラミングの側面を学びましょう。
アルゴリズム
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
擬似コード
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
Cプログラミング言語での選択ソートの実装について知るには、ここをクリックしてください。