선택 정렬 (Selection Sort)

1. 선택 정렬

가장 작은 것을 맨 앞으로 가져오자 !

 

 

2. 선택 정렬 예제

ex )  1  10  5  8  7  6  4  3  2  9  오름차순 정리하시오.

 

#include<stdio.h>


int main(void) {
	int a[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
	int min, minIdx, temp;

	int n = sizeof(a) / sizeof(int);


	for (int i = 0; i < n-1; i++) {
		min = a[i];
		minIdx = i;

		for (int j = i + 1; j < n; j++) {
			if (a[j] < min) {
				min = a[j];
				minIdx = j;
			}	
		}

		temp = a[i];
		a[i] = a[minIdx];
		a[minIdx] = temp;
		
	}

	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}

	return 0;
}

 

 

 

3. 선택 정렬의 시간 복잡도

앞의 예제에서 총 비교 횟수를 대략적으로 살펴보면 다음과 같다. 

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 10 * (10 +1) / 2

 

∴  input이 N개일 때, 선택 정렬의 시간복잡도는 O(N^2)