Selection Sort

선택 정렬은 가장 직관적인 정렬 알고리즘이다. 아마 사람들이 손으로 직접 정렬을 할 때 가장 많이 사용할 것이다.

수들을 오름차순으로 정렬한다고 해보자.
먼저 가장 작은 수를 찾아 맨 앞에 놓은 뒤 나머지 수들에서 똑같은 절차를 반복하면 정렬된 수열을 얻을 수 있다.

이같은 간단한 아이디어를 코드로 구현하면 다음과 같다.

void SelectionSort(int N,int a[]){
	for(int i=0;i<N;i++){
		int pivot = a[i], pos = i;	
		for(int j=i;j<N;j++){
			if(pivot > a[j]){
				pivot = a[j];
				pos = j;
			}
		}
		swap(a[i],a[pos]);
	}
}

이 알고리즘에서는 i번째 최솟값을 찾을 때마다 N-i번의 비교가 필요하며 이 때문에 시간복잡도가 \(\BigO{N^{2}}\)이 된다.

여기서 가장 많은 시간이 소용되는 부분은 최솟값을 찾는 부분이다.
이 방법을 발전시키기 위해서는 최솟값을 빠르게 찾을 수 있어야 하는데 이는 자료구조를 통해 해결할 수 있다. Heap Sort에서는 Heap이라는 자료구조를 사용하여 빠르게 최솟값을 찾아 시간복잡도를 줄인다.

선택 정렬은 다른 \(\BigO{N^{2}}\)정렬에 비해 빠르게 동작한다. 비교 연산이 값을 바꾸는 연산이 더 빠른데 선택 정렬은 비교연산을 많이 하고 값을 바꾸는 연산을 적게 하기 때문이다.