🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
정렬 - 선택 정렬
📍 선택 정렬(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);
👉🏻 버블 정렬과 같은 O(n^2)의 성능을 가짐
📍 선택 정렬의 장단점
👉🏻 장점: 이해와 구현이 쉬움
👉🏻 단점: 성능이 좋지 않음