[알고리즘, C] 선택 정렬(Selection Sort) 구현

<선택 정렬 구현>

[SelectionSort.c]

/*
* 알고리즘 - 선택 정렬(Selection Sort)
* 파일명: SelectionSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 선택 정렬 구현
* 이전 버전 내용:
*/

#include <stdio.h>

void SelectionSort(int arr[], int n)
{
	int i, j;
	int maxIdx; // 우선 순위가 가장 높은 인덱스 값
	int temp;

	for (i = 0; i < n - 1; i++)
	{
		maxIdx = i; // 인덱스 값은 i로. 맨 처음이라면 0부터
		for (j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[maxIdx]) // 오름차순 기준 정렬
				maxIdx = j; // 만약 비교하는 값이 더 작다면 해당 인덱스로 바꾼다.
		}

		// 데이터 교환
		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}

int main()
{
	int arr[4] = { 3, 4, 2, 1 };
	int i;

	SelectionSort(arr, sizeof(arr)/sizeof(int));

	for (i = 0; i < 4; i++)
		printf("%d ", arr[i]);

	printf("\n");

	return 0;
}

 

[선택 정렬의 이해]

선택 정렬은 정렬 순서에 맞게 하나씩 ‘선택’해서 옮기는 알고리즘.
쉽게 말해서 처음부터 끝까지 쭉 훑어보면서 우선순위가 가장 앞서는 데이터를 찾아 가장 왼쪽부터 채운다.

 

"정렬 순서상 가장 앞서는 것을 선택하여 가장 왼쪽으로 이동 시키고,

원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다."

위의 코드를 예시로 든다면, 맨 처음에는 3과 1을 교환하게 된다.
1이 이동하게 되면 1의 자리가 사실상 비는 것이므로 해당 자리에 3을 갖다 놓는 것.
그래서 실제로 보이기에는 교환하는 것처럼 보이게 된다.

 

[성능 평가]

버블 정렬과 마찬가지로 데이터가 $n$개가 있다면 $n-1$단계를 거쳐서 정렬을 수행하게 된다.
선택 정렬에서도 데이터 갯수가 $n$개일 때, 진행이 되는 비교의 횟수는 다음과 같아진다.

$(n-1) + (n-2) + … + 2 + 1$

이는 등차수열의 합으로 표현할 수 있으며, 다음과 같이 계산된다.

$$
\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}
$$

그래서 선택 정렬 또한 비교 연산에 대한 빅-오는 최악의 경우나 최선의 경우 구분 없이 $O(n^2)$이다.
그렇다면 데이터 이동 횟수는 버블 정렬과 같을까? 그렇지는 않다.
버블 정렬과 달리 데이터의 이동은 바깥쪽의 for문에서만 이뤄진다.
그래서 데이터의 이동 횟수의 경우에는 $(n-1)$회의 교환이 이뤄지게 된다.
최악이나 최선의 경우와 상관 없이 $3(n-1)$회 만큼의 이동 연산이 이뤄진다.
그래서 데이터 이동 연산(대입연산)에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 $O(n)$이다.