단순 선택 정렬

지난 글 : [알고리즘/Do it 알고리즘] - 버블 정렬

 

단순 선택 정렬 알아보기

단순 선택 정렬은 가장 작은 요소를 맨 앞으로, 두 번째로 작은 요소를 맨 앞에서 두 번째로 이동하는 등의 작업을 반복하는 알고리즘이다.

참고 : [알고리즘/알고리즘 도감] - 선택 정렬

 

단순 선택 정렬의 교환 과정은 아래와 같다.

1. 아직 정렬하지 않은 부분에서 가장 작은 키값(a[min])을 선택한다.
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

 

아래는 단순 선택 정렬을 수행하는 메서드다.

static void selectionSort(int[] a, int n) {
	for(int i = 0; i < n - 1; i++) {
    		int min = i;
        	for(int j = i + 1; j < n; j++)
        		if(a[j] < a[min])
            			min = j;
            		swap(a, i, min);
    }
}

단순 선택 정렬 알고리즘의 요솟값을 비교하는 횟수는 (n2 - n) / 2번이다. 또, 이 알고리즘은 서로 떨어져 있는 요소를 교환하기에 안정적이지 않다. 만약 정수형 배열에서 단순 선택 정렬 알고리즘을 사용해 정렬할 때, 요소 2개가 값이 3으로 동일하다면 개발자가 만든 식별자(L, R) 등과 상관없이 정렬하므로 정렬 후 요소의 순서가 바뀔 수 있다.

 

참고 서적 :