선택 정렬(Selection Sort)

개념 요약

• Bubble Sort와 유사한 알고리즘이다.
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있으며 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

---

정렬 과정

1. 주어진 배열 중 최솟값을 찾는다.
2. 찾은 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

---

코드

void	selection_sort(std::vector<int> &unsorted_array)
{
	int	temp = 0, min_idx = 0, max = unsorted_array.size();
	// 위치 지정 인덱스
	for (int i = 0; i < max - 1; ++i)
	{
		// 현재 인덱스값 지정
		min_idx = i;
		for (int j = i + 1; j < max; ++j)
		{
			// 대소 비교
			if (unsorted_array[j] < unsorted_array[min_idx])
				min_idx = j;
		}
		// swap
		temp = unsorted_array[min_idx];
		unsorted_array[min_idx] = unsorted_array[i];
		unsorted_array[i] = temp;
	}
}

 

---

시간 복잡도

• 거품 정렬과 동일한 방식으로 최선, 평균, 최악의 경우에 $O(n^2)$이다.

 

---

공간 복잡도

• 주어진 배열 내에 교환으로 정렬이 수행되므로 $O(n)$이다.

 

---

장단점

• 알고리즘이 단순하며, 배열 내부에서 swap 하는 방식으로 추가 메모리가 필요 없다.
• 비효율적이고 불안정한 정렬이다.