n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2)
으로 동일하다.
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)
이다
function solution(arr) {
let answer = arr;
for ( let i = 0; i < arr.length - 1; i++ ) {
// 초기 인덱스 번호 idx에 저장
let idx = i;
for ( let j = i+1; j < arr.length; j++ ) {
// arr[idx] 보다 작은 값 나타나면 그 인덱스를 idx로 바꿔줌
if (arr[j] < arr[idx]) idx = j;
}
// 각 배열을 교환
[arr[i], arr[idx]] = [arr[idx], arr[i]];
}
return answer;
}
let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr))
Bubble sort와 마찬가지로 알고리즘이 단순하다.
정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
시간복잡도가 O(n^2)으로, 비효율적이다.
불안정 정렬(Unstable Sort) 이다.
Bubble Sort와 유사하지만, 조금 더 빠른 Selection Sort에 대해 알아봤다. 기술 면접이나 시험(n번째 회전에 정렬 상태)에서도 종종 나오는 정렬이니 알아두면 좋다.