선택정렬
- 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.
- 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.
의사코드
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item
function solution(arr) {
let answer = arr;
for (let i = 0; i < arr.length - 1; i++) {
let smallestIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[index] > arr[j]) index = j;
}
//새로운 문법
[arr[i], arr[smallestIndex]] = [arr[smallestIndex], arr[i]];
//예전 방법
// let temporary = arr[i];
// arr[i] = arr[smallestIndex];
// arr[smallestIndex] = temporary;
}
return answer;
}
- 배열의 길이가 n이라면 배열의 0번째 index부터 n-1 만큼 반복문을 돌린다
- 배열의 0번째, 첫번째, 두번째 부터 순서대로 정렬해준다
- i=0에 대해 j for문이 돌면(1번째 index부터 비교) 0번째 index에 올바른 숫자가 온다(제일작은수)
- i=1에 대해 j for문이 돌면(2번째 index부터 비교) 1번째 index에 올바른 숫자가 온다(두번째로 작은수) = > 0번째 index는 이미 정렬이 되어 있으니 j for문의 시작은 i+1 이다
- 제일 작은 수의 index가 해당 i 라고 가정하고 시작한다
- 똑바로 정렬되 있다고 가정
- 배열을 돌면서 더 작은수를 만나면 그때 그때 index를 변경해준다
- 배열의 끝까지 돌면 제일 작은수의 index가 저장되고 i와 제일작은수의 index를 바꿔준다
다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다.
6 3 8 5 2 7 4 1
먼저 아래 숫자들 중에서 가장 작은 값을 찾습니다.
6 3 8 5 2 7 4 1
가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환합니다.
1 3 8 5 2 7 4 6
그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾습니다.
1 3 8 5 2 7 4 6
가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환합니다.
1 2 8 5 3 7 4 6
이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료됩니다.
1 2 3 4 5 6 7 8
출처 boostcourse 모두를 위한 컴퓨터 과학
인프런 자바스크립트 알고리즘 문제풀이
Divde & Conquer