[알고리즘] 선택 정렬(Select Sort)

선택 정렬(Select Sort)이란?

제자리 정렬 알고리즘의 하나이다. 

정렬되어 있지 않은 데이터에서 가장 작은 값을 뽑아 가장 앞의 데이터와 교환해 나가는 방식이다.

 

장점

• 구현이 간단하다.
• 비교 횟수에 비해 실제 교환 횟수가 적어 많은 교환이 일어나는 자료의 경우 효율적이다.

단점

• 정렬 시간이 오래걸린다.

 

알고리즘의 순서

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

선택 정렬 그림

---

의사 코드

전체적인 의사코드는 다음과 같다.

for( i = 0 to n - 1){
    for(j = i + 1 to n){
        if(최소값 보다 작은 a[j])
           최소값이 들어있는 인덱스 저장;
    }
    선택된 가장 작은 값과 a[i] 서로 맞바꾼다.;
}

 

알고리즘 구현

void selectSort(vector<int>& list){

    int N = list.size();
    int minIndex = 0;

    for(int i = 0; i < N - 1; i++){
        minIndex = i;

        for(int j = i + 1; j < N; j++){
            if(list[minIndex] > list[j]){
                minIndex = j;
            }
        }

        swap(list[i],list[minIndex]);
    }
}

시간 복잡도

2개의 반복 횟수

• 외부 반복문(N-1)
• 내부 반복문(N)

교환 횟수

• 교환은 상수의 시간(1)

T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

---