[Data Structure] 선택 정렬(selection sort)

---

선택 정렬

 

 

작은 수를 선택해서 앞쪽에 배치하는 정렬 방식이라 선택 정렬이다. 효율적이지는 않지만, 버블 정렬과 함께 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.

정렬은 가장 앞 수를 선택한 후 자신보다 작은 수가 나오면 교환하는 방식으로 진행된다. 끝의 수까지 비교하고, 작을 때 교환했다면 가장 앞에는 리스트에서 가장 작은 수가 올 것이다. 이제 두번째 수를 선택하고 다시 비교, 교환하고, 그 후에는 세번째 수를 선택하고, ... 반복하여 마지막 수 직전에 도달하면 모든 수가 정렬된다.

 

---

예시

 

예를 들어 위와 같은 리스트를 정렬한다고 해보자.

먼저 위와 같이 가장 앞을 선택하고 그 다음 수와 비교한다. 선택된 수인 9가 비교 대상인 2보다 크다.

그러므로 두 수를 바꿔준다. 그 후 아래와 같이 다시 첫번째 자리를 기준으로 그 다음과 비교하고 교환한다.

$$ \vdots $$

반복하여 가장 작은 수를 가장 앞에 놓아 정렬하였다.

다시 반복하여 다음 두번째 자리도 정렬한다.

$$ \vdots $$

반복하면 위와 같이 정렬되었다. 이 과정을 리스트의 크기가 $ n $ 이라 할 때 $ n - 1 $ 번 반복하면 정렬이 끝난다.

예시를 통해 알 수 있듯이 가장 작은 수를 가장 앞으로 보내고, 그 다음 남은 수 중에서 가장 작은 수를 다시 앞으로 보내고, ... 를 반복하여 정렬한다. 큰 수를 뒤로 보내는 방식으로도 바꿀 수 있다.

루프를 두 번 반복하므로 버블 정렬과 마찬가지로 선택 정렬의 시간복잡도는 정렬 상태와 상관없이 $ \mathcal{O}(n^2) $ 이다.

 

---

구현 | C

 

void selection_sort(int list[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int least = i;
        for (int j = i + 1; j < n; j++) {
            if (list[j] < list[least]) {
                least = j;
            }
        }
        if (i != least) {
            int temp = list[i];
            list[i] = list[least];
            list[least] = temp;
        }
    }
}