[Sort] 선택정렬 Selection Sort

정렬

정렬은 알고리즘의 효율성 차이를 극명하게 보여준다.

선택정렬

✏️개념

• 숫자를 오름차순으로 정렬하는 프로그램을 만들어보자

  1, 10, 5, 8, 9, 2, 4, 3, 7, 6

  • 과정

    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 맨 앞의 1을 먼저 선택하여 정렬을 시도한다. 이때, 1이 가장 작으므로 고정
    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 그 다음으로 작은 수는 2이므로 2와 10을 바꾼다.
    1, 2, 5, 6, 9, 10, 4, 3, 7, 6       // 그 다음으로 작은 수는 3이므로 3과 5를 바꾼다.  
    1, 2, 3, 6, 9, 10, 4, 5, 7, 6       // 이런 과정을 반복한다
    ...
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  
  

  • 즉, 선택정렬은 가장 작은 것을 선택하여 앞으로 보낸다

✏️구현

    #include<iostream>
    using namespace std;

    int main(void){
        int min, idx, tmp;
        int len = 10;
        int array[10] = {1, 10, 5, 8, 9, 2, 4, 3, 7, 6};
        
        for(int i = 0; i < len; i++){
            min = array[i];
            for(int j = i; j < len; j++){
                if(min > array[j]){                     // 작은 수를 찾으면 그 값과 인덱스를 저장해준다
                    min = array[j];
                    idx = j;
                }
            }
            // 찾은 가장 작은 수를 가장 앞의 수와 바꿔준다(swap)
            tmp = array[i];
            array[i] = min;
            array[idx] = tmp; 
        }

        return 0;
    }

✏️시간복잡도

• 처음에 10번을 비교하고, 그다음에는 9번 비교하고, 그 다음에는 8번 비교하고…
• 결과적으로 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1이므로 55번 비교했다

따라서, N 개의 수를 정렬하기 위해서 N(N+1)/2번 비교하므로 O(N^2)

• 만약, 정렬해야 할 데이터의 수가 10000개라면 대략 일 억 번 정도를 계산해야한다.
  y = x^2의 그래프를 생각해보면 x(데이터 수)가 늘수록 계산양이 매우 많이 늘어난다. 즉, 선택정렬은 상대적으로 비효율적인 알고리즘이다.