#10 선택정렬(Selection sort)

● 선택정렬(Selection sort)?

- Selection sort 또한 Bubble sort와 마찬가지로 구현이 그다지 어렵지 않은 알고리즘이다.

- 반대로 말하면 Selection sort 또한 Bubble sort와 마찬가지로 성능이 좋다고 할 수는 없다.

- Selection sort는 배열의 정렬되지 않은 영역의 첫 번째 원소(가장 앞 원소)를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다.

 

ex)

[6, 3, 4, 1, 2, 5]

- 위의 배열이 한 번도 Selection sort를 거치지 않은 배열이라고 했을 때 배열의 정렬되지 않은 영역은 아래와 같다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 정렬되지 않은 영역의 첫 번째 원소(index[0] = 6)를 시작으로 마지막 원소까지 비교 후 가장 작은 값은 (index[3] = 1)이기에 (index[3] = 1)과 (index[0] = 6)의 위치를 교체한다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 이후에 정렬된 영역과 정렬되지 않은 영역은 아래와 같이 된다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 다시 한 번 정렬되지 않은 영역의 첫 번째 원소(index[1] = 3)와 마지막 원소까지 비교 후 가장 작은 값(index[4] = 2)을 첫 번째 원소로 가져온다.

- 정렬이 완료된 영역(index[0] = 1)은 더 이상 참조할 필요가 없다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 이후에 정렬된 영역과 정렬되지 않은 영역은 아래와 같이 된다.

- 이러한 작업을 배열의 끝까지 반복하면 그게 바로 Selection sort이다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

[1, 2, 3, 4, 5, 6]  -->  Selection sort가 모두 끝난 후의 모습

---

● Selection sort 구현

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minValueIndex = i; // 정렬되지 않은 영역의 원소 중 최소값을 가지는 원소의 index

        // 정렬되지 않은 영역의 (첫 번째 원소 ~ 마지막 원소)까지 순회하며 가장 작은 값을 찾기 위한 for문
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[minValueIndex]) {
                // 순회 중 arr[minValueIndex] 보다 작은 값을 발견하면 minValueIndex에 해당 원소의 index 값을 저장
                minValueIndex = j;
            }
        }

        let temp = arr[i];
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}

let arr = [4, 2, 1, 3];

console.log("========== 정렬 전 ==========");
console.log(arr);

selectionSort(arr);

console.log("========== 정렬 후 ==========");
console.log(arr);

(arr.length - 1)
- 마지막 원소는 자동으로 정렬이 되기 때문에 배열의 원소가 n개라면 n-1번 반복시킨다.
ex) let arr = [1, 4, 2, 3]
--> arr의 length = 4 이므로 3번만 반복하면 된다.
--> 1번 반복 : [1, 4, 2, 3]
--> 2번 반복 : [1, 2, 4, 3]
--> 3번 반복 : [1, 2, 3, 4]

(let minValueIndex = i;)
- minValueIndex의 값으로 0이 아닌 i 를 넣어주는 이유는
- 반복을 한 번씩 진행할 때마다 최소값이 하나씩 정렬되기 때문에 이미 정렬된 영역은 반복에서 제외하기 위함이다.

(let j = i + 1)
- i의 값은 이미 minValueIndex에 저장했기 때문에 j의 값은 (i + 1)로 설정

---

● Selection sort 성능과 장단점

- Selection sort 또한 Bubble sort와 마찬가지로 바깥쪽 for 문이 실행될수록 안쪽 for 문이 줄어드는 형태이다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 이를 수학식으로 표현하면 위와 같다.

- Selection sort 또한 Bubble sort와 동일한 수식을 가지며 이는 곧 Selection sort의 성능이 O(n^2)라는 것을 의미한다.

- 핵심 계산 부분이 for 문 2개이니 O(n^2) 성능이라는 것을 유추할 수 있다.

Selection sort 장점	Selection sort 단점
Bubble sort 마찬가지로 이해와 구현이 간단	성능이 O(n^2)으로 좋지 않다.