選択ソート(Selection Sort)

1.ソート選択

• insituソートアルゴリズムの1つ
• • で指定されたリストで最小値を探します.
  • その値を一番前の値
  に置き換える.
  • の第1の位置の残りのリスト
  を同様に置換する.
  
比較
• が一定時間で完了すると仮定すると、この方法でn個の所与のリストをソートするには、O(n^2)に相当する時間
が必要となる.
• アルゴリズムは簡単で、利用可能なメモリが限られている場合に性能の優位性を提供する
• 複雑度:
  • 最悪(時間):O(n^2)比較,O(n)交換
  • 最適時間:O(n^2)比較,O(n)交換
  • 平均(時間):O(n^2)比較,O(n)交換
  • 空間複雑度:O(1)スタンバイ

2.首都コード

i를 0부터 n까지 반복:
	배열[i]부터 배열[n-1]까지 차례로 비교
    가장 작은 값이 배열[j]
    배열[i]와 배열[j]의 값을 서로 맞바꿈

3.他のソートと比較

• 泡ソート:時間的複雑度O(n^2)のソートアルゴリズムにおいて、選択ソートは泡ソート
より常に優れている.
• 挿入ソート:挿入ソートは、k回目の繰り返し後、最初のk回目の要素がソート順に表示されるのと同様であり、「ソート」を選択すると、残りのすべての要素を参照してk+1回の要素を検索します.「挿入」「仕上げ」の違いは、k+1個の要素を配置するのに必要な任意の数の要素のみを検索するため、実行効率が高いことです.
• 連結ソート:選択ソートは連結ソートと同じ分割征服アルゴリズムを使用するが、通常は大きな配列よりも小さい(10~20個のアリ)ため、
を最適化するには、十分な小さなサブリストにのみ挿入するか、選択ソートを使用することが望ましい.

4.コード実装

• java

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
    return list;
}

• javascript

function selectionSor(list) {
  let indexMin, tmp;
    
  for(let i=0; i<list.length-1; i++) {
    indexMin = i;
  	for(let j=i+1; j<list.length; j++) {
      if(list[j] < list[indexMin]) {
        indexMin = j;
      }
      tmp = list[indexMin];
      list[indexMin] = list[i];
      list[i] = temp;
    }
  }
  return list;
}