整列選択(Selection Sort)

5153 ワード
テキストリンク

ソートの選択



Selection SortはBubble Sortに似たアルゴリズムで、この順序で要素を配置する位置が決定され、どの要素を入れるかを選択するアルゴリズムです.
SortとInsertionSortの選択を混同する人が多く、Sortを選択して配列内で該当する位置を選択し、該当する値を見つけると便利です.

ソート・プロシージャ

  • で指定された配列で最小値を探します.
    • 値
  • を一番前の値に置き換えます.
  • は、第1の位置を除いた残りの配列を同様の方法で置換する.

    • コード#コード#

    void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}
    まず、位置(inde)を選択します.
  • i+1要素から、選択した位置(index)の値と比較します.
  • の昇順なので、現在選択されている位置の値よりもツアーの値が小さい場合は、位置(index)がリフレッシュされます.
  • "2"号複文終了後、indexminには"1"号で選択された位置(index)の値の位置(index)が含まれているため、互いに交換される.

    • 複雑さと特徴


    時間の複雑さ


  • 1回目の回転の比較回数:1~(n-1)=>n-1

  • 2回目の回転の比較回数:2~(n-1)=>n-2

  • ...

  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
    • 比較が定数時間内に行われると仮定すると,n個の与えられた配列を並べ替えるにはO(n^2)の時間が必要となる.最適,平均,最悪の場合,時間複雑度はO(n^2)である.

    くうかんふくざつさ


    与えられた配列ではスイッチ(Swap)により並べ替えられているのでO(n)となる.

    長所

  • Bubble sortと同様にアルゴリズムは簡単です.
  • ソートの比較回数は多いが、実際の交換回数はBubble Sortに比べて少ないため、大量の交換が必要な資料の状態で比較的効率的である.
  • Bubble sortと同様に、ソートする配列で交換され、他のメモリ領域は必要ありません.

    • 短所

  • 時間複雑度はO(n^2)であり,非効率であった.
  • 不安定なソート.

    • 📝リファレンス


    https://gyoogle.dev/blog/algorithm/Selection%20Sort.html
    [JAVA]変数(基本型、参照型)
    横スクロールdiv