[Algorithm] 선택정렬 알고리즘(Selection Sort Algorithm)

1. 선택정렬

 

선택정렬은 정렬 알고리즘 중 하나로, 내부 비교 정렬이다.

가장 앞의 값을 기준으로 배열 내에서 최소값을 찾고, 해당 값을 가장 앞의 값과 교환한다.

이를 반복하면서 배열을 정렬하는게 선택정렬이다.

 

O(n^2)의 시간복잡도를 갖기 때문에 성능이 떨어지지만 메모리가 절약된다는 장점이 있다. 

또한 데이터가 중복된 경우에도 위치가 바뀔 수 있는 Unstable 정렬이다.

따라서 데이터가 큰 경우보다, 메모리가 제한되는 경우에 사용하는 것이 좋다.

 

Unstable

 

 

 

 

2. 선택정렬 구현

function solution(arr) {
    let answer = arr;
    for (let i = 0; i < arr.length; i++) {
        let idx = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[idx]) idx = j;
        }
        [arr[i], arr[idx]] = [arr[idx], arr[i]];
    }
    return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

자바스크립트로 선택정렬을 구현하는 방법을 알아보자.

선택정렬은 최소값을 찾아 첫 번째 값과 교환하는 알고리즘이라는걸 생각하면 구현하기 어렵지 않다.

 

for (let i = 0; i < arr.length; i++) { ... }

 

우선 요소를 처음부터 끝까지 비교해야 하기 때문에 for문을 사용해준다.

 

let idx = i;
for (let j = i + 1; j < arr.length; j++) {
    if (arr[j] < arr[idx]) idx = j;
}

 

최소값의 index를 저장할 idx를 만들어주고, for문을 한 번 더 사용해준다.

이제 i의 다음 요소(=j)와 최소값을 비교해서 가장 작은 값의 인덱스를 idx에 넣어준다.

 

값이 아니라 인덱스를 넣어주는 이유는, 해당 값과 첫 번째 값을 교환해야 하기 때문이다.

인덱스 번호를 알아야 교환이 가능하다.

 

[arr[i], arr[idx]] = [arr[idx], arr[i]];

 

그 후 첫 번째 값(arr[i])과 최소값(arr[idx])을 교환해준다.

위 교환 방식은 구조분해할당을 이용한 것이다. 

(arr[i]에 arr[idx]를, arr[idx]에 arr[i]를 할당)

 

 

*구조분해할당

 

구조분해할당은 배열이나 객체의 속성을 해제하여 그 값을 개별 변수에 담을 수 있게 하는 것을 말한다.

let arr = ["Bora", "Lee"]
let [firstName, surname] = arr

//firstName : Bora
//surname : Lee

 

 

* 참고

 

https://im-developer.tistory.com/133

https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/sorting/selection-sort/README.md