출처: Wikipedia

선택 정렬은 첫번째 요소부터 순환하며 자신의 뒤쪽에 위치한 요소(정렬되지 않은 요소)들 중 최솟값을 찾아 선택하여 스왑하는 형태로 정렬이 진행됩니다.

선택 정렬 또한 버블 정렬과 같이 직관적이고 구현이 비교적 쉽지만 마찬가지로 성능이 좋지 않습니다.

구현

아래 로직은 오름차순으로 정렬한다는 가정하에 작성하였습니다.

// 최솟값을 찾아 현재 요소와 스왑
function selectionSort(arr) {
    const n = arr.length;

    for(let i = 0; i < n-1; i++) {
        // 최솟값의 인덱스를 찾기 위해 선언하는 변수로
        // 값 비교를 위해 일단 현재 인덱스를 할당
        let minIndex = i;

        // 최솟값을 찾아야 하므로 i이후의 모든 요소들을 순환해야 한다.
        for(let j = i + 1; j < n; j++) {
            if(arr[j] < arr[minIndex])  {
              minIndex = j;
            }
        }

        // Swap
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }

    return arr;
}

console.log(selectionSort([5, 2, 4, 1, 3]));

선택 정렬은 최솟값을 찾기 위해 이미 정렬된 요소를 제외한 모든 요소를 다 순환해야 하므로 최선, 평균, 최악 모두 O(n^2)이라는 일정한 시간 복잡도를 가집니다.

또한, 버블 정렬의 경우 오름차순으로 정렬 할 때 가장 오른쪽에 위치 할 최댓값부터 정렬되지만 선택 정렬의 경우 반대로 왼쪽에 위치 할 최솟값부터 정렬된다는 특징이 있습니다.