선택 정렬이란?

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. (출처 : 위키)

가장 작은것을 선택해서 맨 앞으로 보낸다고 생각하자.

과정설명

1. 주어진 리스트에서 최솟값을 찾는다.
2. 최솟값을 리스트의 맨 앞 (i 값) 값과 교체한다.
3. 마지막 리스트 원소까지 반복한다.

C언어 코드

#include<stdio.h>

int main() {
	int i, j, min, index, temp;
	int array[10] = { 10,5,1,9,8,4,6,2,3,7 };

	for (i = 0; i < 10; i++) {
		min = 9999; // 임의의 min 값
		for (j = i; j < 10; j++) {
			if (min > array[j]) { //최솟값 찾기
				min = array[j];
				index = j;
			}
		}
		temp = array[i]; //i 의 위치와 index 의 위치 swap
		array[i] = array[index];
		array[index] = temp;
	}
	
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
}

시간 복잡도 (Big O)

선택정렬은 등차수열로 나타낼 수 있다.
위의 코드에서 처럼 원소가 10개라면
10 + (10 + 1)/2 = 55 로 나타 낼 수 있다.

하지만 원소가 1억개, 그 이상이라면?

무수히 많기 때문에 덧셈과 2로 나누는것을 생각하지 않아도 된다.
즉, N*N 으로 나타 낼 수 있다.

따라서 시간복잡도는 O(N^2) 이 된다.