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

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

 

데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘이 존재합니다.

그 중에서 선택 정렬은 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬입니다.

 

1   9   4   6   11   10   3   15   2   13

 

위와 같은 수가 있을 때 수들을 오름차순하는 선택 정렬을 해보겠습니다.

먼저, 첫번째 원소인 1부터 마지막 원소인 13까지 반복하면서 최솟값을 찾아냅니다.

찾은 후 그 값을 배열의 맨 앞 원소와 교환하고 정렬을 확정합니다.

위 배열에서는 1이 최솟값이므로 그대로 1이 정렬로 확정됩니다.

 

그 다음 반복에서는 확정된 정렬을 제외한 나머지 원소 배열에서 최솟값을 찾은 후 그 값을 다시 확정된 정렬을 제외한 나머지 원소 배열의 맨 앞 원소와 교환하고 정렬을 확정합니다.

 

1   9   4   6   11   10   3   15   2   13

1   2   4   6   11   10   3   15   9   13

1   2   3   6   11   10   4   15   9   13 

. . .

1   2   3   4   6   9   10   11   13   15 

 

알고리즘 구현

// Algorithm Analysis
// 선택 정렬(Selection Sort) : 가장 작은 것을 선택하여 앞으로 보낸다.

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i, j, min, index, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 10; i++) {
		min = INT_MAX;
		for (j = i; j < 10; j++) {
			if (min > arr[j]) {
				min = arr[j];
				index = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	return 0;
}

 

시간 복잡도 : O(N * N)

= 10 + 9 + 8 + ... + 1 = 10 * (10 + 1) / 2 = 55
= N * (N + 1) / 2 
= N * N
= O(N * N)

 

매 반복마다 10번, 9번, 8번 ... 1번 반복하기 때문에 선택 정렬의 시간 복잡도는 O(N * N)으로써 데이터 수가 1000개라면 1000000번 반복해야 하기 때문에 다소 비효율적인 정렬입니다. 

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.