29. Selection Sort

선택 정렬(Selection Sort)은 버블 정렬과는 다르게 비교 관계가 바뀐 쌍을 발견해도 바로 바꾸지 않고 마지막 값까지 확인한 다음 최솟값을 찾아서 제자리에 넣는 과정을 반복한다. 맨 처음에는 $1\text{~}n$번째 원소 중 가장 앞에 오는 것을 찾아서 첫 번째 원소와 바꾸고, 다음에는 $2\text{~}n$번째 원소 중 가장 앞에 오는 것을 찾아서 두 번째 원소와 바꾸고, 같은 방법으로 $(n-1)\text{~}n$번째 원소까지 확인하게 되면 정렬이 완료된다.

 

다음은 이전 글에 예시로 나온 정렬을 C++에서 선택 정렬로 구현한 코드이다.

for(k = 1; k < n; k++)
{
    for(i = m = k; i <= n; i++)
    {
        if(a[i] < a[m])m = i;
    }
    swap(a[k], a[m]);
}

다음은 선택 정렬 과정을 시뮬레이션한 것이다.

이 방법 역시 $\Theta(n^2)$의 시간복잡도를 갖는다.

 

→ solved.ac tag: sorting