[C언어] 정렬 알고리즘 개요와 선택 정렬

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 10 5 8 7 6 4 3 2 9

가장 작은 것을 선택해서 자리를 바꾼다. => 선택정렬
1. 1은 가장 작지만 맨 앞에 있으므로 그대로 둔다.
2. 그 다음 작은 수는 2이므로 10과 자리를 바꾼다. → 1 2 5 8 7 6 4 3 10 9
3. 3과 5의 자리를 바꾼다. → 1 2 3 8 7 6 4 5 10 9
4. 4와 8의 자리를 바꾼다. → 1 2 3 4 7 6 8 5 10 9
5. 5와 7의 자리를 바꾼다. → 1 2 3 4 5 6 8 7 10 9
6. 7과 8의 자리를 바꾼다. → 1 2 3 4 5 6 7 8 10 9
7. 9와 10의 자리를 바꾼다. → 1 2 3 4 5 6 7 8 9 10 (정렬 완료)

#include <stdio.h>

int main(void){
	int i, j, min, index, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for(i = 0; i < 10; i++){
		min = 9999;
		for(j = i; j < 10; j++){
			if(min > array[j]){
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	} 
	for(i = 0; i < 10; i++){
		printf("%d ", array[i]);
	}
	return 0;
}

 

위 알고리즘의 수행시간은? => 선택정렬의 시간 복잡도 구하기

1부터 10까지 정렬하고 > 2부터 10까지 정렬하고 . . . > 10을 정렬한다.
10 + 9 + ... + 1
=> 10 * (10 + 1) / 2 = 55 (등차수열 공식)
=> N * (N + 1) / 2
<N이 아주 크다고 가정>
=> O(N * N)