[자료구조] Select Sort

Select sort는 정렬이 되지 않은 전체 배열에서 하나를 선택하여 위치를 교환하는 정렬방법이다.
 

1) 7[0] 을 선택한 뒤 배열 [1]~[6] 까지 중 가장 작은 수를 선택한다. 가장 작은 수 = 1[6]

2) 가장 작은 수 1[6]과 7[0]의 자리를 swap 한다.

3) 그다음 4[1]를 선택한 뒤 배열 [2]~[6] 가장 작은 수를 선택한다. 가장 작은 수 = 2[5]

4) 끝에 도달할 때 까지 반복한다.

ex)

  void sort(int *a, const int n)
  { // Sort the n integers a[0] to a[n-1] into nondecreasing order.
     for (int i = 0; i < n; i++)
     {
        int j = i;
        // find smallest integer in a[i] to a[n-1]
        for (int k = i + 1; k < n; k++)
           if (a[k] < a[j]) j = k;
        swap(a[i], a[j]);
    }
 }