[알고리즘] 단순 선택 정렬

단순 선택 정렬

단순선택정렬은 가장 작은 요소부터 선택하여 알맞은 위치에 옮겨 정렬하는 알고리즘이다.

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다.
2. 선택된 가장 작은 키값을 정렬하지 않은 부분의 첫번째 요소와 교환한다.

다음과 같은 배열이 있다.
6 4 8 3 1 9 7

먼저 가장 작은 값을 선택한다. ( 1 선택 )
이후 정렬되지 않은 부분에서 가장 앞의 요소 (6)와 교환한다.

가장 작은 값을 선택하는 것은 선형 검색으로 찾는다.

public static void selectionSort(int[] a, int n) {
	for(int i=0; i<n-1; i++) {
		int min = i; //min은 최소값이 아니다. 최소값의 인덱스
		for(int j = i+1; j<n; j++) {
			if(a[j] < a[min]) {
				min = j;
			}
		}
		swap(a,min,i);
	}
}

단순선택정렬은 서로 떨어져 있는 요소를 교환하기 때문에 안정적이지 않은 정렬 알고리즘에 속한다.