[Algorithm] 선택 정렬(Selection Sort)

정렬이란?

데이터 배열을 내림차순 혹은 오름차순 순으로 다시 나열하는 것을 정렬이라고 합니다.

선택 정렬이란?

선택 정렬은 가장 작은 데이터를 선택하여 앞으로 보내는 정렬입니다.

예시를 살펴보겠습니다.

1 10 6 3 9 5 8 2 4 7

이렇게 10개의 원소를 가진 배열이 존재한다고 가정해보겠습니다.

먼저 첫번째 원소인 1부터 시작하여 제일 작은 숫자를 첫번째 원소 위치에 가져옵니다.
위의 경우는 1이 제일 작으므로 1을 고정시켜줍니다.

그 다음으로는 두번째 원소인 2부터 시작하여 제일 작은 숫자를 찾아줍니다.
2가 제일 작기 때문에 두번째 위치에 10 대신 2를 가져와서 고정시켜줍니다.

다음과 같은 과정을 열번째 원소까지 반복해주면됩니다.

코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int main() {
	int arr[10] = { 1, 10, 6, 3, 9, 5, 8, 2, 4, 7 };

	int min, temp, index;

	for (int i = 0; i < 10; i++) {
		min = 9999;
		for (int j = i; j < 10; j++) {
			if (min > arr[j]) {
				min = arr[j];
				index = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}

	for (int i = 0; i < 10; i++) {
		cout << arr[i] << " ";
	}
}

시간 복잡도

매 반복마다 10번, 9번, ... 1번 반복합니다.
이는 원소의 개수 n개 만큼 1+2+..+n 까지 더한 등차수열과 같으므로
$n(n+1)/2$ 이 됩니다.

즉 $O(n^2)$ 입니다.