javascript 코딩테스트 - 선택 정렬(selection sort)

저번에 살펴본 버블 정렬 bubble sort가 최댓값을 맨 뒤에 확정지을 때까지 스왑을 하는 거였다면 선택 정렬 selection sort는 최솟값을 맨 앞에 확정 짓는 것을 반복하는 것이다.

 

마찬가지로 순서대로 원리를 살펴보자.

1. 배열을 돌면서 최솟값을 찾는다.

2. 최솟값을 찾은 후에 그 원소와 배열의 맨 앞 원소의 위치를 바꿔준다.

3. 그러면 확정된 최솟값을 제외한 나머지 원소들에 대해 똑같은 과정을 반복한다.

 

예를 들어 [5, 3, 4, 1, 2]가 있다고 해보자.

 

그러면 처음에 5만 살펴보면 최솟값은 5로 설정된다.

(최솟값 = 5)

 

그 다음 3을 살펴보면 5보다 작기 때문에 최솟값은 3으로 업데이트 된다.

(최솟값 = 3)

 

그 다음 4를 살펴보면 3보다 크기 때문에 최솟값은 바뀌지 않는다.

(최솟값 = 3)

 

그 다음 1을 살펴보면 3보다 작기 때문에 최솟값은  1로 업데이트된다.

(최솟값 = 1)

 

그 다음 2를 살펴보면 1보다 크기 대문에 최솟값은 바뀌지 않는다.

 

그러면 이제 최솟값인 1의 원소와 배열의 맨 앞 원소인 5의 위치를 바꿔준다.

 

[1, 3, 4, 5, 2]

이제 1이 최솟값이라는 걸 확정 지었으니 나머지 3, 4, 5, 2에 대해서만 같은 과정을 반복한다.

 

이렇게 반복문 사이클을 돌면

 

[1, 2, 4, 5, 3]

 

[1, 2, 3, 5, 4]

 

[1, 2, 3, 4, 5]

 

[1, 2, 3, 4, 5]

 

이렇게 해서 정렬이 완료가 된다.

 

이 원리를 코드로 구현해보자.

function sortSelect(arr) {
	// 배열의 원소만큼 반복문을 돌면서 최솟값을 하나씩 확정
    for(let i=0;i<arr.length;i++){
    
        let min=Infinity;
        let idx;
        
        // 반복문을 돌면서 최솟값을 결정 짓고 그 인덱스를 저장
        for(let j=i;j<arr.length;j++){
            if(arr[j] < min){
                min = arr[j]
                idx = j
            }
        }
        
        // 최솟값을 가진 원소를 앞에 배치시킴
        [arr[i],arr[idx]] = [arr[idx],arr[i]]
        
    }
    return arr
}

밖의 for 문은 원소를 하나씩 확정지어야하기 때문에 배열의 원소의 개수만큼 반복문을 돌도록 구성했다.

그 다음 최솟값을 찾는 알고리즘은 확정짓고 남은 원소들의 개수만큼 반복문을 돌면서 min값과 그 idx 값을 찾도록 한다.

 

처음에는 아무 원소도 확정짓기 않았기 때문에 arr.length 만큼 돌아야하지만

하나씩 찾아갈 때마다 반복문의 구간의 길이가 작아져야하므로 j=i로 설정한다.

 

그 다음은 최솟값을 찾은 후에 원소를 스왑하는 과정이다.

 

시간 복잡도를 따지면 for 문이 2번 중첩되어있으므로 O(n^2)이다.

 

이전에 살펴본 버블 정렬과 목표하는 값이 최댓값이냐 최솟값이냐의 차이일뿐 구성은 거의 똑같다고 볼 수 있다.

개인적으로는 선택 정렬이 좀 더 직관적이라고 생각된다.

 

하지만 뒤에서 O(nlogn)인 정렬 알고리즘이 등장할테니 좀만 더 기다려보자.