정렬 알고리즘 - 선택 정렬
August 13, 2022
JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트
선택 정렬 (Selection Sort)
선택 정렬은 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있으며, 어떤 원소를 넣는지 선택하는 알고리즘이다.
첫 번째 루프에서는 최솟값을 첫 번째 위치에 넣고, 두 번째 루프에서는 남은 값들 중 최솟값을 두 번째 위치, ...
정렬 과정
[19, 44, 38, 5, 47, 15]
배열을 오름차순으로 정렬해보자.
- 1회전: [19, 44, 38, 5, 47, 15]
- 첫 번째 값(19)을 최솟값(5)을 탐색해 교환
- 1회전 결과: [5, 44, 38, 19, 47, 15]
- 2회전: [5, 44, 38, 19, 47, 15]
- 두 번째 값(44)을 최솟값(15)을 탐색해 교환
- 2회전 결과: [5, 15, 38, 19, 47, 44]
- 3회전: [5, 15, 38, 19, 47, 44]
- 세 번째 값(38) 보다 작은 최솟값이 없음으로 교환하지 않음
- 3회전 결과: [5, 15, 19, 38, 47, 44]
- 4회전: [5, 15, 19, 38, 47, 44]
- 네 번째 값(47)을 최솟값(44)을 탐색해 교환
- 2회전 결과: [5, 15, 19, 38, 44, 47]
의사코드
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j;
}
}
if (i !== lowest) {
let temp = arr[i];
arr[i] = arr[lowest];
arr[lowest] = temp;
}
}
return arr;
}
selectionSort([34, 22, 10, 19, 17]); // [10, 17, 19, 22, 34]
시간 복잡도
- Best: O(n2)
- Worst: O(n2)
- Average: O(n2)