선택 정렬 구현해보기

선택 정렬

최솟값을 찾아 데이터 영역의 가장 앞으로 이동하는 방식을 반복하여 전체 데이터 영역을 정렬하는 알고리즘

가장 작은 원소를 선택하여 정렬하는 알고리즘

각 회차마다 원소를 넣을 위치가 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하여 정렬하는 알고리즘

평균 시간 복잡도 O(n^2)

장점

정렬을 위한 비교 횟수는 많지만, 교환하는 횟수가 상당히 적다.

따라서 교환이 많이 이루어지는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식이다.

배열 내에서 교환하는 방식(제자리 정렬, in-place sort)이므로 다른 메모리 공간을 필요로 하지 않는다.

단점

정렬을 위한 비교 횟수가 많다.

이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보인다.

중복된 원소의 순서가 정렬 후에도 유지되지 않으므로 unstable 정렬이다.

class SelectionSort {
    sort(data) {
        let len = data.length;
        // 선택 정렬에서 N - 1 회전이 종료되면 마지막 데이터도 자동 정렬이 완료되기에 len - 1
        for (let i = 0; i < len - 1; i++) {
            let minIdx = i; // i회전에 i번째 원소가 최솟값임을 가정
            for(let j = i; j < len; j++) {
                if (data[minIdx] > data[j]){
                    minIdx = j;
                }
            }
            // 최솟값이 있는 index를 찾으면 해당 minIdx와 현재 위치 i를 swap
            [data[i], data[minIdx]] = [data[minIdx], data[i]];
        }
        return data;
    }
}