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

 원리 

1. 정렬되지 않은 중 원소를 가장 작은 원소를 탐색하자

2. 가장 작은 원소를 정렬 되지 않은 원소 맨앞으로 보내자

 

 [ 70, 55, 30, 20, 47 ]

 

|    70, 55, 30, 20, 47 --> 70, 55, 30, (20), 47 (선택)

20, |    70, 55, 30, 47 --> 20,  70, 55, (30), 47 (선택)

20, 30, |    70, 55, 47 --> 20, 30,  70, 55, (47) (선택)

20, 30, 47, |    70, 55 --> 20, 30, 47,  70, (55) (선택)

 

정렬 후 : [ 20, 30, 47, 55, 70 ]

 

 구현 

for (int i = 0; i < n - 1; ++i)
{
	int min_idx = i;
	for (int j = i + 1; j < n; ++j)
		if (arr[min_idx] > arr[j]) min_idx = j;
	arr[min_idx] ^= arr[i];
	arr[i] ^= arr[min_idx];
	arr[min_idx] ^= arr[i];
}

 

다음은 "정렬되지 않은 원소중 최솟값"의 인덱스를 찾아서 앞에서 부터 차례대로 정렬 중인 i번째 인덱스와 스왑을 하며 정렬을 하고 있습니다.

 

위는 오름차순으로 정렬한 것이고, 내림차순을 위해서는 반대로 "최댓값"을 찾아서 "정렬되지 않은 원소 맨 앞"으로 보내는 과정을 반복하면 됩니다.

 

 시간복잡도 

다음과 같이 정렬되지 않은 원소는 처음 0번에서 n-1번까지 탐색하게 되고 

정렬되지 않은 arr[i+1] ~ arr[n-1]에서 최솟값을 찾기 위해 순회 하므로 O(n^2)의 시간복잡도를 가지게 됩니다.

 

 정리 

이름	BEST	AVG	WORST	RUN TIME(정수 60,000)
버블 정렬	n^2	n^2	n^2	확인
선택 정렬	n^2	n^2	n^2	사진 참고

선택 정렬 런타임 (랜덤 정수 60,000개)

5개로 테스트 결과 12.8000s ~ 13.9000s 사이로 나옵니다.

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

 참조 

위키백과 - 선택 정렬

선택 정렬 - 위키백과, 우리 모두의 백과사전