선택 정렬은 배열의 첫 요소 부터 선택하여 배열 끝까지 다른 요소들과 비교하면서 다른 요소들 중 선택한 요소보다 작은 값(최솟값)이 있을 경우 서로의 위치를 바꾼다(최솟값을 맨 앞에 둔다).
선택 정렬은 arr[0] 요소와 다른 요소들을 비교하여 다른 요소가 arr[0] 보다 작을 경우 그 요소와 arr[0] 요소의 위치를 바꾼다. 이번엔 arr[1] 요소와 다른 요소들을 비교하여 다른 요소가 arr[1] 보다 작을 경우 서로의 위치를 바꾼다. 이 작업을 배열의 마지막 요소까지 반복한다.
의사 코드
- 배열의 첫 번째 요소를 최솟값으로 저장한다.
- 저장한 최솟값 보다 더 작은 숫자를 찾을 때까지 저장한 최솟값과 배열의 다음 요소들과 비교한다.
- 더 작은 숫자가 발견되면 더 작은 숫자를 새로운 최솟값으로 저장하고 배열이 끝날 때까지 계속 다시 찾는다.
- 최소값이 처음 시작한 값(인덱스)이 아닌 경우 두 값의 위치를 바꾼다.
- 배열이 정렬될 때까지 다음 요소를 최솟값으로 저장하여 이 과정을 반복한다.
// selection sort
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
// 최솟값의 index 설정
let lowest = i;
// arr[i]의 다음 요소(arr[i + 1])들과 비교하면서
for (let j = i + 1; j < arr.length; j++) {
// 먼저 지정한 최솟값보다 더 작은 값이 나오면
if (arr[j] < arr[lowest]) {
// 더 작은 값의 index를 최솟값의 index로 변경한다.
lowest = j;
}
}
// 배열의 끝까지 비교한 후 처음 지정한 최솟값과 중간에 찾은 최솟값의 위치를 바꾼다.
let temp = arr[i];
arr[i] = arr[lowest];
arr[lowest] = temp;
}
return arr;
}
console.log(selectionSort([6, 5, 7, 4, 1, 3])); // [1, 3, 4, 5, 6, 7]