선택 정렬

선택 정렬

숫자를 한번에 하나씩 비교하며 최솟값을 찾는 작업을 반복하고 반복이 끝난 마지막에 찾은 최솟값과 비교한 요소의 위치를 교환한다. 배열의 전체 길이만큼 순서대로 작업을 반복한다. 선택 정렬의 시간 복잡도는 O(n^2)으로 배열의 길이가 길어질수록 완료 시간도 늘어난다.

선택 정렬 함수

function selectionSort(arr) {
    const swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            // 최솟값을 가진 인덱스가 달라지면 업데이트
            if (arr[j] < arr[min]) min = j;
            // 반복을 시작한 첫번째 요소가 최솟값이 아니면 위치 교환
            if (i !== min) swap(arr, i, min);
        }
    }
    return arr;
}

✍️ <JavaScript 알고리즘 & 자료구조 마스터클래스> 강의를 들으며 알게 된 내용을 정리하였습니다.