선택 정렬(Selection Sort)

개요

정렬(Sort) 문제는 알고리즘 공부의 가장 기초가 된다. 이는 효율성 또는 시간 복잡도의 차이를 명확하게 보여주기 때문이다. 그렇기에 이 글에서는 정렬 방법 중 가장 기초가 되는 선택 정렬을 소개하고 구현해보고자 한다.

선택 정렬

"3 1 2 9 8 4 7 10 5 6
위 숫자들을 오름차순으로 정렬하라."

이 문제에서 가장 간단한 해결 방법은 정렬하지 않은 숫자들 가운데 가장 작은 숫자를 찾아 순서대로 위치시키는 방법일 것이다. 이렇게 조건에 부합하는 하나를 찾아 순서대로 정렬하는 방법을 흔히 선택 정렬이라 한다.

수행 과정

선택 정렬 과정은 다음과 같다.
1. [3, 1, 2, 9, 8, 4, 7, 10 ,5, 6]를 index 0번째부터 순서대로 값을 비교하며 가장 작은 값(현재는 '1')을 찾아낸다. 이때 내부 for문의 반복 횟수는 9번이다.
2. 이 숫자를 가장 왼쪽에 위치하는 숫자(현재는 '3')와 서로 교체한다. 이를 스왑(swap)이라 한다.
3. 재배치한 '1'을 제외한 [3, 2, 9, 8, 4, 7, 10, 5, 6]에서 1번 과정을 다시 수행한다. 이때 내부 for문의 반복 횟수는 8번이다.
4. 1~3번 과정을 모두 재배치할때까지 반복한다. 이때 외부 for문의 반복 횟수는 9번이다.

시간 복잡도

위 과정을 모두 반복했을 때의 시간 복잡도는 9 x 8 x 7 x ... x 1이 되며 수식으로 표현하면 N * (N - 1) / 2가 된다. N이 1을 무시할 수 있을 만큼 충분히 큰 숫자라면 시간 복잡도는 O(N^2)이 된다.

코드 구현

선택 정렬을 코드로 구현하면 다음과 같다.

#include <iostream>

int array[10] = {3, 1, 2, 9, 8, 4, 7, 10, 5, 6};

int main() 
{
	int min, min_index, temp;
	
	for (int i = 0; i < 9; i++) {
		min = array[i];
		for (int j = i+1; j < 10; j++) {
			if (min > array[j]) {
				min = array[j];
				min_index = j;
			}
		}

		if (min != array[i]){
			temp = array[i];
			array[i] = min;
			array[min_index] = temp;
		}
	}

	std::cout << "array : ";
	for (int i = 0; i < 10; i++) {
		std::cout << array[i] << ' ';
	}

	return 0;
}
//array : 1 2 3 4 5 6 7 8 9 10

Reference

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221226800661&navType=by