알고리즘 : 선택정렬(Selection sort)

선택정렬(Selection sort)이란?

버블정렬은 맨 앞부터 하나씩 올라가며 위치를 찾아가는 방법이라면 선택정렬은 맨 아래부터 값을 쌓아가는 정렬 방식을 뜻합니다.

 

예를 들어, 배열을 한 바뀌씩 돌면서 가장 값이 낮은 값을 찾아내 0번 인덱스에 배치하고, 남은 정렬을 다시 순회하면서 그중에서 가장 값이 낮은 원소를 그 다음 인덱스인 1번에 배치하는 것을 반복합니다. 즉 계속해서 최솟값을 찾아내 스왑해 주는 것 입니다. 

 

작동 방식은 다음과 같습니다:

1. 주어진 배열에서 최솟값을 찾습니다.
2. 그 최솟값을 맨 앞에 위치한 값과 교환합니다.
3. 맨 처음 위치를 제외한 나머지 배열을 같은 방법으로 교체합니다.
4. 하나의 원소만 남을 때까지 위의 과정을 반복합니다.

이를 코드로 구현하면 선택정렬은 다음과 같습니다.

function selectionSort(array) {
	let indexMin, temp;
    
    for (let i = 0; i < array.length; i++) {
    	indexMin = i
        for (let j = i + 1; j < array.length; j++) {
        	if (arrav[j] < array[indexMin]) {
            	indexMin = j; // 최솟값 찾기
            }
        }
        
        // 배열에서 찾은 최솟값과 i번 인덱스와 스왑
        temp = array[indexMin]; 
        array[indexMin] = array[i];
        array[i] = temp;
    }
}

let array = [64, 34, 25, 12, 22, 11, 90];
selectionSort(array);

 

동작과정

입력 배열: [64, 34, 25, 12, 22, 11, 90]

첫 번째 반복 (i = 0)

1. indexMin = 0 (64)
2. j를 통해 전체 배열을 순회하며 최솟값 찾기
   1. 34 < 64? → indexMin = 1
   2. 25 < 34? → indexMin = 2
   3. 12 < 25? → indexMin = 3
   4. 22 < 12? → 유지
   5. 11 < 12? → indexMin = 5
   6. 90 < 11? → 유지
3. 11(array[5])과 64(array[0])를 교환 결과: [11, 34, 25, 12, 22, 64, 90]

두 번째 반복 (i = 1)

1. indexMin = 1 (34)
2. 남은 배열에서 최솟값 찾기
   • 25 < 34? → indexMin = 2
   • 12 < 25? → indexMin = 3
   • 22 < 12? → 유지
   • 64 < 12? → 유지
   • 90 < 12? → 유지
3. 12(array[3])와 34(array[1])를 교환 결과: [11, 12, 25, 34, 22, 64, 90]

이런 식으로 계속 진행되어

• 세 번째: [11, 12, 22, 34, 25, 64, 90]
• 네 번째: [11, 12, 22, 25, 34, 64, 90]
• 다섯 번째: [11, 12, 22, 25, 34, 64, 90]
• 여섯 번째: [11, 12, 22, 25, 34, 64, 90]