선택 정렬(Selection Sort)

주어진 배열에서 가장 작은 숫자를 앞으로 옮겨가며 정렬하는 방법이다.

#include <climits> 는 자료형의 최대, 최소값이 정의된 헤더파일이다.

#include <iostream>
#include <climits>
using namespace std;

int main() {
	int min, idx, tmp, arr[10] = {10,5,4,6,2,3,7,9,1,8};
	for(int i = 0; i < 10; i++) {
		min = INT_MAX;
		for(int j = i; j < 10; j++) {
			if(min > arr[j]) {
				min = arr[j];
				idx = j;
			}
		}
		tmp = arr[i];
		arr[i] = arr[idx];
		arr[idx] = tmp;
	}
	for(int i = 0; i < 10; i ++)
		cout << arr[i] << " ";
}

흔히 ‘정렬’이라는 주제를 떠올렸을 때 가장 직관적으로 떠올릴 수 있는 방법 중 하나인 만큼 비 효율적이다.

알고리즘의 성능을 분석할 때 시간복잡도라는 척도를 사용한다고 한다.

n개의 수를 정렬한다면


위 식을 빅 오 표기법으로 나타내면 O(n^2) 가 된다.

algorithm	average	worst	best	space
select	O(N^2)	O(N^2)	O(N^2)	O(1)