선택 정렬(Selection Sort)

선택 정렬(Selection Sort)이란?

전체 리스트를 왼쪽 리스트와 오른쪽 리스트로 구분한 뒤, 오른쪽 리스트에서 가장 작은 레코드를 꺼내어 왼쪽 리스트의 오른쪽 끝에 넣는 방법.

이때, 왼쪽의 리스트는 정렬된 리스트이고 오른쪽 리스트는 정렬할 리스트로 가정한다.

 

(7, 3, 9, 4, 1, 6)을 삽입 정렬로 정렬한 순서

왼쪽 리스트	오른쪽 리스트	설명
(7)	(3, 9, 4, 1, 6)	초기 상태
(1)	(3, 9, 4, 7, 6)	1 선택 후 7과 교환
(1, 3)	(9, 4, 7, 6)	3 선택 후 3과 교환
(1, 3, 4)	(9, 7, 6)	4 선택 후 4와 교환
(1, 3, 4, 6)	(9, 7)	6 선택 후 6과 교환
(1, 3, 4, 6, 7)	(9)	7 선택 후 7과 교환
(1, 3, 4, 6, 7, 9)	()	9 선택 후 9와 교환

 

선택 정렬의 장점

이동 연산이 (n - 1)번만 필요하므로 큰 레코드의 정렬에 유리.

선택 정렬의 비교횟수

삽입 정렬은 레코드의 수가 n일 경우 (n-1)번의 삽입을 필요로 하며, 매ㅓㄴ 삽입할 때마다 정렬된 리스트의 레코드를 비교해서 삽입될 위치를 찾아야 한다.

이때 필요한 평균 비교횟수는 이미 정렬된 왼쪽 리스트의 크기의 반으로 가정할 수 있으며, 그 크기는 1, 2, 3, ..., (n-2), (n-1)과 같이 증가한다.

 

 

 

선택정렬의 이동횟수

레코드의 수가 n일 경우 최소값을 (n - 1)번 선택해야 한다. 따라서 이동 횟수는 (n - 1)이다.

 

시간복잡도

 

선택정렬 코드 (Java)

public int[] sort() {
        int temp = 0;
	for(int i = 0; i < array.length - 1; i++) {
		min = i;
		for(int j = i + 1; j < array.length; j++) {
			if(array[j] < array[min]) {
				min = j;
			}
		}
			
		temp = array[i];
		array[i] = array[min];
		array[min] = temp;
	}
	
	return array;
}