선택 정렬이란?
대상 데이터에서 최솟값 (혹은 최댓값)을 찾고, 남은 정렬의 가장 앞에 있는 데이터와 교환하는 알고리즘을 가진 정렬이다.
선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)로 비효율적이기 때문에 자주 사용하지는 않는다.
선택 정렬의 과정
1. 남은 정렬 부분에서 최솟값(혹은 최댓값)을 찾는다.
2. 남은 정렬에서 가장 앞에 있는 데이터와 선택된 데이터를 교체한다.
3. 가장 앞에 있는 데이터의 위치를 변경해서(index++) 남은 정렬 부분의 범위를 줄이다.
4. 전체 데이터 크기만큼 인덱스가 커질 때까지 (남은 정렬 부분이 없어질 때까지) 반복한다.
(이때 마지막 요소는 자동 정렬되므로 반복 횟수는 n-1이다.)
이를 코드로 구현하면 다음과 같다.
1. arr의 길이-1 만큼 반복문을 돌린다.
2. 최솟값의 인덱스를 담을 변수를 선언하여 i를 할당한다.
3. j를 i+1 ~ 리스트 길이만큼 반복문을 돌린다.
4. 만약 arr[j]가 arr[minIdx]보다 작다면 최솟값 인덱스에 j를 저장한다.
5. 만약 최솟값 인덱스가 다른 값(j)으로 바뀌었다면 arr[i]와 arr[j]를 swap 해준다 function selectionSort(arr) {
for (let i=0; i<arr.length-1; i++) {
let minIdx = i
for (let j=i+1; j<arr.length;j++) {
if(arr[j]<arr[minIdx]){
minIdx = j; //남은 정렬에서 최솟값의 인덱스를 찾는 과정
}
}
if(minIdx !== i ) {
//가장 앞의 데이터(arr[i])와 선택된 데이터(arr[minIdx])교체
[arr[i], arr[minIdx]] = [arr[minIdx],arr[i]];
}
}
return arr;
}