선택정렬
큰 값을 배열 마지막 인덱스에 위치시키는 버블정렬과 달리, 작은 값을 한 번에 하나씩 위치시킨다.
기준 값과 나머지 원소들을 전부 순회하며 비교하여, 가장 작은 값과 자리를 바꾼다.
의사코드
- 최솟값 인덱스를 저장할 변수 필요. 초기값은 시작하는 기준 값과 동일하게 설정해주면 될 듯.
- 기준값부터 나머지 원소를 순회하며 최소값 인덱스를 갱신, 저장
- 기준값과 최소값 교환
- 원래 기준값 다음 인덱스부터 1,2,3 과정 반복
구현
function selectSort(arr) {
for (var i = 0; i <= arr.length; i++) {
var minIdx = i;
for (var j = i; j <= arr.length; j++) {
if (arr[minIdx] > arr[j]) {
minIdx = j;
}
}
if (arr[i] > arr[minIdx]) {
let tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
return arr;
}
const arr = [4, 24, 52, 34, 34, 54, 63, 24, 543, 3432, 52];
삽입정렬
한 번에 하나의 항목을 올바른 위치에 삽입하여 정렬된 부분을 점진적으로 구축
이미 정렬된 그룹에 새로운 값이 들어오는 상황에서 강점을 갖는다. 라이브 스트리밍 등 실시간으로 데이터를 집계하는 경우 효율적으로 사용할 수 있을 듯 하다.
의사코드
- 배열의 두 번째 요소를 선택. 첫 번째 요소는 정렬된 부분으로 간주하여, 이와 비교 후 크기에 맞게 삽입
- 다음 요소로 이동하여, 앞에서 정렬한 두 요소와 비교해 올바른 위치에 삽입
- 배열의 끝까지 해당 과정을 반복
구현
function insertSore(arr) {
for (var i = 1; i < arr.length; i++) {
var currentVal = arr[i];
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = currentVal;
}
}
const arr = [4, 24, 52, 34, 34, 54, 63, 24, 543, 3432, 52];
버블, 선택, 삽입정렬 비교
| 분류 | 시간복잡도 (최선 / 최악) | 시간복잡도 (평균) | 공간복잡도 |
| 버블정렬 | O(n) / O(n^2) | O(n^2) | O(1) |
| 삽입정렬 | O(n) / O(n^2) | O(n^2) | O(1) |
| 선택정렬 | O(n) / O(n^2) | O(n^2) | O(1) |
