선택 정렬
선택 정렬(selection sort)
수열을 정렬하는 알고리즘 중 하나. 제자리 정렬 알고리즘.
시간 복잡도: O(n2)
다음과 같이 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야한다.
[ 9, 6, 7, 3, 5 ]
알고리즘은 선형 탐색해서 최소값을 찾는다. 최소값을 찾은 뒤 열의 왼쪽 끝에 있는 값과 교환한뒤 정렬을 완료한다.
[ 3, 6, 7, 9, 5 ] - 한번 회전
참고로 최소값이 이미 왼쪽 끝에 있다면 아무런 작업도 하지 않는다.
동일한 작업을 모든 숫자가 정렬을 마칠 때까지 반복한다.
[ 3, 5, 7, 9, 6 ] - 두번 회전
[ 3, 5, 6, 9, 7 ] - 세번 회전
[ 3, 5, 6, 7, 9 ] - 네번 회전
장단점
- 장점
- 자료 이동 횟수가 미리 정의된다.
- 단점
- 안정성을 만족하지 않는다. 즉, 같은 값의 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
버블정렬과 비슷하지만 가장 큰 값이 "버블링"되지 않고 가장 작은 값만 선택해 정렬한다.
선택정렬(selection sort) js 코드
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let lowest = arr[i];
let lowestIndex = i;
for (let j = i; j < arr.length; j++) {
if (arr[j] < lowest) {
lowest = arr[j];
lowestIndex = j;
}
}
let temp = arr[i];
arr[i] = arr[lowestIndex];
arr[lowestIndex] = temp;
}
return arr;
};