Selection Sort

Selection Sort

void selectionSort(int arr[], int n){
    int tmp;
    int minIdx;
 
    for(int i=0;i<n-1;++i){
        minIdx = i;
        for(int j=i+1;j<n;++j){
            if(arr[minIdx] > arr[j]){
                minIdx = j;
            }
        }
 
        tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

• 선택 정렬은 unstable 정렬이다. 예를 들어 2 2 1 3 과 같은 배열을 선택 정렬을 하면, 1 2 2 3 이다. 
  이 때, 2 2 1 3 을 B b A C 라 치면, 선택 정렬 결과는 B와 A가 swap 되어 A b B C 가 된다.
  같은 값인 2 2 가 정렬되고 나서 기존의 순서 B b에서 b B 순서로 변경되었기 때문에 선택정렬은
  unstable sort 라고 한다. unstable 하다라는 뜻은 항상 순서가 변경된다가 아닌, 순서 유지를 보장하지 못한다는 뜻이다.
• 최선, 평균 시간 복잡도가 O(n^2) 로 느린 정렬이며, 같은 복잡도인 버벌소트보다는 항상 더 빠른 속도를 지닌다.
  ( swap 의 빈도가 현저히 적기 때문이다 )
• in-place 정렬이므로 공간복잡도는 O(n) 이다,
• i번 째 라운드에 i번 째 idx 부터 탐색하면서 제일 작은 값을 지닌 배열의 인덱스를 갱신고서,
  N-i 자리와 arr[minIdx] 값을 swap 한다. 한 라운드에 swap 이 1번만 일어난다!