[알고리즘] 선택 정렬 알고리즘

1. 정의

- 선택 정렬(Selection Sort) 알고리즘은 잘못된 위치의 원소를 찾아 그 원소를 올바른 위치로 옮겨 주는 원소 교환(Exchange)기법을 사용하여 정렬을 수행한다. 따라서 가장 작은 원소를 찾아 첫 번째 위치의 원소와 교환하고, 다음으로 작은 원소는 두 번째 원소와 교환하는 방식으로 정렬을 수행한다.

2. 알고리즘

SelectionSort(a[], n)

for(i <- 1; i < n; i <- i + 1) do {

배열 a[i], ... , a[n] 중에서 가장 작은 원소 a[k]를 선택;

a[k]를 a[i]와 교환;

}

end SelectionSort()

3. 동작 과정

패스	테이블	최소값
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

(표 출처 : 위키백과 - 선택 정렬)

- 테이블(배열)에서 최소값을 찾아 가장 앞의 원소와 위치를 바꾼다.

- 다음엔 두 번째, 세 번째 ... 원소와 위치를 변경한다.

- 위 작업을 반복 수행하고, 더이상의 변경이 없을 때 정렬을 끝낸다.

4. 특성

(1) 시간 복잡도

- 선택 정렬 알고리즘은 N개의 원소 각각 N-1번의 비교를 해야 하기 때문에 전체 비교 횟수가 N(N-1) / 2가 되어 시간 복잡도는 O(N^2)이 된다.

(2) 입력 순서 민감도

- 입력 순서에 관계 없이 항상 처음부터 끝까지 비교를 하기 때문에 입력 순서에 민감하지 않다.

(3) 제자리 정렬 여부

- 추가적인 기억장소를 요구하지 않으므로 제자리 정렬이다.

(4) 안정성

- 레코드의 상대적인 위치가 유지되지 않을 수도 있으므로 불안정적인 알고리즘이다. (ex : 동일한 값이 존재할 때의 처리)

5. 소스코드 (C언어)

void SelectionSort(int a[], int n)
{
    int i = 0, j = 0, min = 0, temp = 0;
    
    for(i = 1; i < n; i ++)
    {
        min = i;
        
        for(j = i + 1; j <= n; j ++)
        {
            if(a[j] < a[min])
                min = j;
        }
    
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}