개념

• 가장 기초적인 알고리즘
• 전체 범위에서 차례대로 가장 작은 숫자를 탐색하고, 가장왼쪽부터 차례대로 교환하는 방식.
• 전체 범위를 돌며 작은 숫자를 선택하여 정렬하는 것이므로 선택 정렬이라고 한다.

이해

왼쪽부터 시작하며, 외부 변수에 시작하는 기준 값과 인덱스를 반환하고, 전체 범위를 탐색하는 탐색 값은 왼쪽부터 비교하면서, 탐색한 값이 기준 값 보다 작다면 탐색 값과 인덱스를 외부 변수에 기준 값과 인덱스를 반환한다.

이어서 전체 범위를 탐색할 때 까지 계속 이어 나가고, 첫번째 탐색이 완료가 되면 외부 변수에 저장된 인덱스와 왼쪽에 시작된 인덱스를 두고 스왑한다.

두번째 탐색도 다음 인덱스를 시작으로 위와 같이 반복한다.

과정1 (시작 값, 기준 값 지정)

과정2

과정3 (기준 값 재지정)

과정4

과정5

과정6

과정7 (시작 값, 기준값 스왑)

과정8

코드

function selectionSort(arr) {
	let size = arr.length;
	for(let i = 0; i < size - 1; i++) {
		let minIdx = i;
		for(let j = i + 1; j < size; j++) {
			if(arr[j] < minIdx) {
				minIdx = j;
			}
		}
		swap(arr, i, minIdx);
	}
}

특징과 시간 복잡도

• 장점: 자료 이동 횟수가 미리 결정된다. (n개 이면 n번만 스왑한다.)