선택정렬은 정렬 알고리즘 중에 가장 직관적이고 이해하기 쉬운(?) 알고리즘 입니다. 작동 방법을 살펴보면
예를 들어 살펴보겠습니다. [9,1,7,8,4,3,0,2]의 배열을 선택정렬로 배열한다고 하면 아래와 같은 방법으로 정렬됩니다.
테이블 최솟값
[9,1,7,8,4,3,0,2] 0
[0,1,7,8,4,3,9,2] 1
[0,1,7,8,4,3,9,2] 2
[0,1,2,8,4,3,9,7] 3
[0,1,2,3,4,8,9,7] 4
[0,1,2,3,4,8,9,7] 7
[0,1,2,3,4,7,9,8] 8
[0,1,2,3,4,7,8,9] 정렬 완료
선택정렬의 복잡도는 O(n^2)입니다. 상당히 느리기 때문에 정렬에서 자주 사용되지는 않습니다.
function selectionSort(arr) {
let i, j, temp, minIndex;
for(i = 0; i < arr.length- 1; i++) {
minIndex = i; // 기준값으로 첫번째 값을 설정한다.
for(j= i+1; j < arr.length; j++) { // 나머지 배열중에 최솟값의 위치를 찾는다
if(arr[minIndex] > arr[j]) {
minIndex = j
}
}
temp = arr[minIndex]; // 찾은 최솟값을 임시 배열에 담는다
arr[minIndex] = arr[i] // 기존 최솟값 위치에 기준값을 담는다
arr[i] = temp; // 기준값은 최솟값으로 바꾼다
}
return arr
}
console.log(selectionSort([5,1,4,7,2,6,8,3])) // [1,2,3,4,5,6,7,8]
잘못된 부분이 있으면 언제든 말씀해주세요.