[자료 구조와 알고리즘] 정렬 - 선택 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

정렬 - 선택 정렬

📍 선택 정렬(Selection Sort)

👉🏻 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가지고 옴

<------ 영역 ----->
[6, 3, 4, 1, 2, 5] // 정렬되지 않은 영역(전체)를 순회 후 가장 작은 값 찾음: 1
 _        _
[1, 3, 4, 6, 2, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴

// 1은 정렬 완료

    <--- 영역 --->
[1, 3, 4, 6, 2, 5] // 순회 후 가장 작은 값 찾음: 2
    _        _
[1, 2, 4, 6, 3, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴

// 2까지 정렬 완료 
       <-- 영역 -->
[1, 2, 4, 6, 3, 5] // 순회 후 가장 작은 값 찾음: 3
       _     _
[1, 2, 3, 6, 4, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴

// 3까지 정렬 완료

...

[1, 2, 3, 4, 5, 6] // 정렬 끝

📍 선택 정렬의 구현

[ selection_sort.mjs ]

function SelectionSort(arr) {
    // 마지막 원소는 자동 정렬되기 때문에 n-1번 반복
    for(let i = 0; i < arr.length - 1; i++) {
        let minValueIndex = i;
        // 반복문 1번 진행할 때마다 최소값 1개가 정렬되므로 정렬된 영역은 반복에서 제외하기 위해 i로 설정
        
        for(let j = i + 1; j < arr.length; j++) {
            // i는 minValueIndex이므로 i+1부터 진행
            if(arr[j] < arr[minValueIndex]) {
                minValueIndex = j;
            }
        }
        // minValueIndex에는 가장 작은 값이 저장되어 있음
        // 이를 정렬되지 않은 원소의 첫 번째 원소와 교체
        
        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);