データ構造とアルゴリズムの選択ソート
選択ソートは単純なソートアルゴリズムです。このソートアルゴリズムは、リストが左端のソートされた部分と右端のソートされていない部分の2つの部分に分割されるインプレース比較ベースのアルゴリズムです。最初は、ソートされた部分は空であり、ソートされていない部分はリスト全体です。
ソートされていない配列から最小の要素が選択され、左端の要素と交換され、その要素がソートされた配列の一部になります。このプロセスは、ソートされていない配列境界を1要素右に移動し続けます。
このアルゴリズムは、平均および最悪の場合の複雑さがΟ(n 2)であるため、大規模なデータセットには適していません。n アイテムの数です。
選択ソートはどのように機能しますか?
次の図の配列を例として考えてみましょう。
ソートされたリストの最初の位置については、リスト全体が順番にスキャンされます。現在14が格納されている最初の位置で、リスト全体を検索し、10が最低値であることがわかります。
したがって、14を10に置き換えます。1回の反復の後、リストの最小値である10が、ソートされたリストの最初の位置に表示されます。
33が存在する2番目の位置では、リストの残りの部分を線形にスキャンし始めます。
14がリストの2番目に低い値であり、2番目に表示されるはずです。これらの値を交換します。
2回の反復の後、2つの最小値がソートされた方法で先頭に配置されます。
同じプロセスが、配列内の残りのアイテムに適用されます。
以下は、ソートプロセス全体の図解です。
それでは、選択ソートのプログラミングの側面をいくつか学びましょう。
アルゴリズム
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 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[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
Cプログラミング言語での選択ソートの実装については、ここをクリックしてください。