선택 정렬이란?
선택 정렬은 배열을 순회하면서 가장 작은 값을 선택하여 배열의 앞쪽으로 이동시키는 정렬 알고리즘이다.
시간 복잡도
- O(n^2)
작동 원리
- 정렬되지 않은 부분 배열에서 최솟값을 선택
- 선택한 최솟값을 배열의 가장 앞에다 놓는다.
- 위 과정을 반복하여 배열이 정렬될 때까지 진행한다.
예시로 [5,3,4,1,2] 배열을 선택 정렬로 정렬한다면
초기 선택: [1], [5, 3, 4, 2]
두 번째 선택: [1, 2], [5, 3, 4]
세 번째 선택: [1, 2, 3], [5, 4]
네 번째 선택: [1, 2, 3, 4], [5]
최종 선택 정렬 결과: [1, 2, 3, 4, 5]
코드
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
const temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
const array = [5, 3, 4, 1, 2];
selectionSort(array);
console.log(array); // [1, 2, 3, 4, 5]