[Udemy] 선택 정렬(Selection Sort)이란?

정의

요소를 비교하여 최솟값을 앞쪽으로 이동시켜 정렬하는 방법으로, 시간 복잡도는 O(n^2)이다.

외부 반복문 1회당 swap이 1회 발생하는 특징이 있다.

 

코드

function selectionSort(arr) {
    function swap(arr, idx1, idx2) {
        [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]    
    }
    
    for (let i = 0; i < arr.length - 1; i++) {
        let min = i
        for (let j = i+1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        swap(arr,i,min)
    }

    return arr;
}

 

swap 함수를 따로 추출해서 사용했다.

외부 반복문 변수 i를 선언하고 마지막 요소 이전까지 순회한다.

i는 최소값 인덱스와 값을 swap 시킬 것이다.

 

중첩 반복문 j는 i 이후 요소부터 순회하면서

i 위치의 요소보다 더 작은 값이 등장할 때, 최솟값 인덱스(min)을 수정한다.

 

중첩 반복문이 끝나면 최솟값 인덱스와 i를 swap 한다.

 

최적화 코드

만약 i 요소가 이미 최솟값이라면 어떨까?

input: [0, 2, 10, 5, 3, 6]

 

i와 min 값을 콘솔에 출력해보자.

 

i와 min 값이 동일할 때에는 굳이 swap을 해줄 필요가 없다.

해당 로직을 코드에 추가하자.

 

function selectionSort(arr) {
    function swap(arr, idx1, idx2) {
        [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]    
    }
    
    for (let i = 0; i < arr.length - 1; i++) {
        let min = i
        for (let j = i+1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        if (i !== min) {
            swap(arr,i,min)
        }
    }

    return arr;
}

 

참조

Udemy - Js 알고리즘 & 자료구조 강의