Selection Sort 선택정렬

안녕하세요. 주인장 H입니다. 

오늘은 선택정렬에 대해서 알아볼건데요. 

1~10 까지 무질서한 숫자를 오름차순으로 정렬한다. 라고 한다면 

선택정렬은 가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까? 라는 고민에서 시작했습니다. 

가장 기초적인 정렬이라고 할 수 있습니다. 

 

선택정렬은 대략 N* (N+1)/2 번의 연산을 수행하는데요. 

빅 오 표기법으로 하게된다면  O(N^2)가 됩니다. 

즉, 선택 정렬의 시간 복잡도는 O(N^2). 

// 1 ~ 10 까지 정렬 하기 
#include<stdio.h>
int main(void) {
	int arr[10] = { 1,3,2,5,7,6,10,9,8,4 };

	int i, j, index, temp;

	for (i = 0; i < 10; i++) {
		int min = 11;
		for (j = i; j < 10; j++) {
			if (arr[j] < min) {
				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;
}