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

선택 정렬(Selection Sort)

선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 1번째 값을 2번째 값부터 마지막 값까지 비교해 최솟값을 찾는다.

2. 1번째 값과 최솟값의 위치를 바꾼다.

3. 2번째 값을 3번째 값부터 마지막 값까지 비교해 최솟값을 찾는다.

4. 2번째 값과 최솟값의 위치를 바꾼다.

5. (N-1)번째 값까지 위 과정을 반복한다.

선택 정렬 예제

입력자료	5	2	8	1	9	7
Step 1	1	2	8	5	9	7
Step 2	1	2	8	5	9	7
Step 3	1	2	5	8	9	7
Step 4	1	2	5	7	9	8
Step 5	1	2	5	7	8	9
출력 결과	1	2	5	7	8	9

입력자료	11	9	5	18	27	15
Step 1	5	9	11	18	27	15
Step 2	5	9	11	18	27	15
Step 3	5	9	11	18	27	15
Step 4	5	9	11	15	27	18
Step 5	5	9	11	15	18	27
출력 결과	5	9	11	15	18	27

소스 코드

void selection_sort(int a[], int n){
        int i,j,min, index;
        for(i=0;i<n-1;i++){
                min = a[i];
                index = i;
                for(j=i+1;j<n;j++){
                        if(min > a[j]){
                                min = a[j];
                                index = j;
                        }
                }
                a[index] = a[i];
                a[i] = min;
        }
}

값이 들어있는 배열 a[]와 길이 n이 입력되었을 때의 소스코드이다.

첫 번째 반복문은 i=0부터 i=n-2까지 진행된다. 그리고 두 번째 반복문은 j=i+1부터 j=n-1까지 진행된다.

첫 번째 반복문에서 min은 a[i]를 저장하고 index는 i로 저장한다. 이후 반복문을 통해 최솟값과 그 위치를 저장한다.

반복문이 종료되었을 때 a[index]에는 a[i]를 a[i]에는 min을 저장해 위치를 서로 바꾼다.

시간복잡도

선택 정렬은 두 개의 반복문이 진행된다.

첫 번째 반복문은 n-1번 반복되고, 두 번째 반복문은 n-1,n-2,...,2,1번 반복된다.

이를 수열로 나열하면 T(n)=(n-1)+(n-2)+...+2+1=n(n-1)/2가 나오고 Big-O 표기법으로 표현하면 O(n^2)이다.