[자료구조/C] 선택 정렬(selection sort)

선택 정렬이란?

오름차순으로 정렬할 경우, 가장 작은 숫자를 선택하여 왼쪽으로 이동하거나 가장 큰 숫자를 선택하여 오른쪽으로 이동하는 정렬 방법이다. (내림차순의 경우, 가장 작은 숫자는 오른쪽으로, 가장 큰 숫자는 왼쪽으로 이동한다)

 

즉, 배열에서 최소값을 찾아 이 최소값을 배열의 첫 번째 요소와 교환하고 그 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하여 두 번째 요소와 교환한다. (최대값을 찾아 배열의 마지막 요소와 교환하고 그 당므에는 마지막 요소를 제외한 나머지 요소들 중에서 가장 큰 값을 선택하여 마지막에서 두 번째 요소와 교환한다.) 이 과정을 (배열의 크기-1) 만큼 반복하여 배열이 모두 정렬될 때까지 반복한다.

 

최소값을 찾아 교환하는 방식

 

void selection_sort(int list[], int n) { //n: 배열의 크기
	int i, j;

	for (i = 0; i <n-1; i++) { //n-1만큼 반복
		int min = list[i];
		int min_idx = i;
		for (j = i+1; j < n; j++) { //왼쪽 요소를 차례대로 제외
			if (min > list[j]) {
				min = list[j]; //왼쪽 요소를 제외한 나머지 요소들중에서 최소값 탐색
				min_idx = j; //최소값의 인덱스
			}
		}
		int num = list[i];
		list[min_idx] = num;
		list[i] = min; //왼쪽 요소와 교환
	}
}

 

최대값을 찾아 교환하는 방식

void selection_sort(int list[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++) { //n-1번 반복
		int max = list[0];
		int max_idx = 0;

		for (j = 0; j < n-i ; j++) { //최대값 찾고
			if (max < list[j]) {
				max = list[j];
				max_idx = j;
			}
		}
		int num = list[n - i - 1]; 
		list[max_idx] = num;
		list[n - i - 1] = max; //맨 오른쪽과 교환
	}
}

 

시간복잡도

배열의 크기가 n일 경우, 

비교	교환
n-1번	1번
n-2번	1번
n-3번 ....	1번 ...
1번	1번

 

즉 비교의 총 횟수는 n-1+n-2+....1 = n(n-1)/2이고, 교환의 총 횟수는 n-1번이다.

차수가 가장 큰 항만을 고려했을 때 시간 복잡도는 O(n^2)이다.