Data-structures-algorithms-selection-sort-algorithm

データ構造とアルゴリズムの選択ソート

選択ソートは、単純なソートアルゴリズムです。 このソートアルゴリズムは、リストが2つの部分、左端のソート済み部分と右端の未ソート部分に分けられるインプレース比較ベースのアルゴリズムです。 最初は、ソートされた部分は空で、ソートされていない部分はリスト全体です。

ソートされていない配列から最小の要素が選択され、左端の要素と交換され、その要素がソートされた配列の一部になります。 このプロセスは、ソートされていない配列の境界を1要素右に移動し続けます。

このアルゴリズムは、その平均および最悪の場合の複雑さがΟ（n ^ 2 ^）であるため、大きなデータセットには適していません。ここで、 n はアイテムの数です。

選択ソートの仕組み

例として、次の配列を考えてみましょう。

Unsorted Array

ソートされたリストの最初の位置では、リスト全体が順番にスキャンされます。 現在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

Copy

疑似コード

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

Copy

Cプログラミング言語での選択ソートの実装については、リンク：/data_structures_algorithms/selection_sort_program_in_c [ここをクリック]をご覧ください。