[Programming/Algorithm] 선택 정렬(Selection Sort)

선택 정렬은 버블 정렬보다도 쉽고 간단한 알고리즘이다. 선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘이다.

정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다.

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

void SelSort(int arr[], int n) {
    int maxIdx;
    int temp;

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

        // 최솟값 탐색
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[maxIdx]) {
                maxIdx = j;
            }
        }

        // 교환
        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp;
    }
}


int main() {
    int arr[4] = { 3, 4, 2, 1 };

    SelSort(arr, sizeof(arr) / sizeof(int));

    for (int i = 0; i < 4; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

1 2 3 4

*/

---

선택 정렬(Selection Sort): 성능평가

선택 정렬의 코드만 봐도 버블 정렬과 성능상 큰 차이가 없음을 알 수 있다. 그럼 비교횟수의 확인을 위해 선택 정렬의 일부인 다음 반복문을 보자.

for(int i=0; i<n-1; i++){
  maxIdx = i;
  for(int j=i+1; j<n; j++){
    if(arr[j] < arr[maxIdx]){
      maxIdx = j;
    }
  }
  ...
}

위의 코드에서 바깥쪽 for문의 i가 0일 때 안쪽 for문의 j는 1부터 n-1까지 증가하여 선택 정렬의 비교 연산은 n-1회 진행된다. 그리고 바깥쪽 for문의 i가 1일 때는 안쪽 for문의 j가 2부터 n-1까지 증가하여 선택 정렬의 비교연산은 n-2회 실행된다. 즉 비교연산의 횟수는 다음과 같이 정리가 가능하다.

(n-1) + (n+2) + ... + 2 + 1

그런데 이는 버블 정렬의 경우와 똑같다. 따라서 선택 정렬의 빅-오 역시 최악의 경우와 최선의 경우 구분 없이 다음과 같다.

O(n의 2제곱)

언뜻 생각하기엔 버블 정렬보다 나은 성능을 보장할 것처럼 보였는데, 비교횟수를 기준으로 보면 차이가 없음을 알 수 있다. 그렇다면 데이터의 이동횟수도 버블 정렬과 차이가 없을까? 여기에는 제법 차이가 있다.

버블 정렬이나 선택 정렬이나 데이터의 교환을 위한 세 번의 대입 연산이 다음과 같은 유형으로 진행된다.

temp = A;
A = B;
B = temp;

하지만 존재하는 위치가 다르다. 버블 정렬의 경우에는 안쪽 for문에 속해있다. 반면 선택 정렬의 경우에는 바껕쪽 for문에 속해있다. 때문에 선택 정렬의 경우 n-1회의 교환이 이뤄지므로 데이터의 이동횟수는 이의 세 배인 3(n-1)이 된다. 따라서 선택 정렬의 데이터 이동연산에 대한 빅-오는, 최악의 경우와 최선의 경우 구분 없이 다음과 같다.

O(n)

최악의 경우를 놓고 보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있겠지만, 버블 정렬은 최선의 경우에 단 한 번의 데이터 이동도 발생하지 않는다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지는 않는다는 사실을 감안하면, 이 둘의 우열을 가리는 것은 무의미하다고 할 수 있다.