선택 정렬(Selection Sort)

• 선택 정렬(Selection sort)

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

1. 정렬되지 않은 부분에서 가장 작은 키의 값을 선택

2. 아직 정렬하지 않은 부분의 첫 번째 요소와 교환

이 과정을 n-1회 반복

 

void selection(int a[], int n) {
	int i, j;
	for (i = 0; i < n - 1; i++) {
		int min = i;
		for (j = i + 1; j < n; j++)
			if (a[j] < a[min]) min = j;
		swap(a[i], a[min]);
	}
}

 

시간복잡도: O(n^2) - best, avg, worst 모두 동일