선택 정렬🧺

소개

Selection sort(선택 정렬)는 제자리 정렬 알고리즘의 하나로 가장 작은(혹은 가장 큰) 원소를 찾아서 교체하는 알고리즘이다. 말 그대로 원소를 선택해서 정렬한다.

 

정렬 과정

다음과 같이 다섯 개의 정수가 주어졌을 때, Selection sort로 오름 차순으로 정렬해보겠다.

 

+-----+-----+-----+-----+-----+
|  5  |  4  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+

 

우선 인덱스 0을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 1부터 원소 끝까지 순회하면서 가장 작은 원소를 찾는다. 그리고 찾은 원소를 가장 처음 원소와 교체한다.

 

+-----+-----+-----+-----+-----+
|  1  |  4  |  5  |  3  |  2  |
+-----+-----+-----+-----+-----+

 

가장 작은 원소가 처음 원소와 교체됐기 때문에 다음 단계부터는 인덱스 1을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 2부터 원소 끝까지 순회하면서 가장 작은 원소를 인덱스 1의 원소와 교체한다.

 

+-----+-----+-----+-----+-----+
|  1  |  2  |  5  |  3  |  4  |
+-----+-----+-----+-----+-----+

 

이어서 동일한 방법으로 시작 위치를 한 칸씩 증가시키면서 가장 작은 원소와 교체해주면 된다.

 

+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  5  |  4  |
+-----+-----+-----+-----+-----+

+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+

 

알고리즘 분석

비교 횟수

선택 정렬은 한 번의 순회가 끝나면 다음 순회는 비교 대상이 하나씩 줄어든다. 전체 원소의 개수가 n개면, 총 (n - 1) 번 검사를 했을 때 한 번 정렬이 완료된다.

 

앞 선 예제에서 총 원소가 5개 이므로, 4 + 3 + 2 + 1 = 10번 검사하면 전체 정렬이 완료된다. 이를 수식으로 일반화하면 다음과 같다.

 

$$
(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = \frac{n(n - 1)}{2}
$$

 

자리 교환 횟수

최선의 경우(이미 정렬된 원소들이 주어지는 경우), 자리 교환이 일어나지 않아서 시간 복잡도에 영향이 없다.

 

그러나 최악의 경우(역순 정렬된 원소들이 주어지는 경우), 순회 횟수 만큼 자리 교환이 일어난다.

 

구현

void selection_sort(int *array)
{
	int temp, minIndex;

	for (int i = 0; i < SIZE - 1; i++)
	{
		minIndex = i;
		for (int j = i + 1; j < SIZE; j++)
		{
			if (array[minIndex] > array[j])
				minIndex = j;
			print_array(array);
		}

		temp = array[i];
		array[i] = array[minIndex];
		array[minIndex] = temp;
	}
}

 

정리

선택 정렬과 거품 정렬은 언뜻 비슷해보인다. 그러나 거품 정렬은 최악의 경우 인접한 모든 원소마다 자리 교환이 일어나지만, 선택 정렬은 비교만 거품 정렬과 동일하게 할 뿐 교환은 순회 당 한 번이다. 이러한 이유로 선택 정렬이 거품 정렬 보다 항상 우수하다.