[#2] 선택 정렬 (Selection Sort)

선택 정렬이란?

선택 정렬(Selection Sort)는 불안정 정렬 알고리즘 중 하나이다.
시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
메모리가 제한적인 환경에서 주로 사용되는 제자리 정렬(in-place sort)이다.

 

- 선택 정렬이 불안정 정렬인 이유

[5, 5, 2, 1] 을 선택 정렬로 1회전 정렬해본 것을 가정해보자.
1회전 후 정렬하게 되면 [1, 5, 2, 5] 가 될 것이다. 이는 기존의 5, 5의 순서가 뒤바뀜을 알 수 있다.
기존의 동일한 숫자인 5, 5의 순서가 뒤바뀌었으므로 선택 정렬은 불안정 정렬에 해당한다.

 

 

 

구현 방법

특정 원소의 위치를 저장하고 전체 값중 가장 작은 값 또는 큰 값을 저장한 위치에 기록하며 정렬해가는 정렬 방식입니다.

 

 

 

---

의사 코드

1. 첫 번째 인덱스부터 마지막 인덱스까지 탐색한다.
   1. 탐색 중인 인덱스를 저장할 인덱스로 기록한다.
   2. 이전에 저장된 인덱스를 제외하고 모든 원소들중 가장 크거나 작은 값을 찾는다.
   3. 저장할 인덱스에 값을 저장한다.

 

 

 

---

소스 코드

void SelectionSort(char* input, int size)
{
	if (input == 0 || size <= 1)
		return;

	int i, j;
	int nPrev, nMin;
	for (i = 0; i < size; ++i)
	{
		nPrev = i;
		nMin = nPrev;
		for (j = i + 1; j < size; ++j)
		{
			if (input[j] < input[nMin])
			{
				nMin = j;
			}
		}
		if (nMin != nPrev)
		{
			SWAP(input[nMin], input[nPrev], char);
		}
	}
}

 

 

 

---

시간 복잡도

T(n) = (n-1) + (n-2) + (n3) ... + 1
T(n) = (n-1) * n/2 이므로,
O(n) = n^2 이다. (최고차항만 취급하므로)

 

 

 

---

안정성 제자리

값이 동일할 경우 순서가 뒤바뀔 수 있으므로 선택정렬은 불안정 정렬(Unstable Sort)이다.
또한, 기존 배열 이외에 추가적인 메모리를 사용하지 않으므로 제자리 정렬(in-place sort)이다.

 

 

 

---