Algorithms/Sorting/Selection Sort

Selection Sort

選択ソート

Outline

選択ソートはある場所に入れるべき値を選択していくソート法である.
挿入ソートは値を基準に場所を選ぶが、選択ソートは場所を基準に値を選ぶ.
選択ソートはデータがどんな並びでも、&mimetex( \sum_{i=0}^{n-1} i);回の比較が必要になる.

Program

サイズnの配列dataに対して選択ソートを行う関数.

void selection_sort(int data[], int n) {
  int min;

  for(int i = 0 ; i < n - 1 ; i++) {
    min = i;

    for(int j = i + 1 ; j < n ; j++) {
      if(data[j] < data[min]) {
        min = j;
      }
    }

    swap(data[i], data[min]);
  }
}

Consideration

#mimetex( \Theta(n^2) )