삽입 정렬
삽입 정렬(insertion sort)
수열을 정렬하는 알고리즘 중 하나. 손 안의 카드를 정렬하는 방식과 유사.
시간 복잡도:
- Best: O(n)
- Worst: O(n2)
다음과 같이 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야한다.
[ 8, 5, 6, 2, 4 ]
처음에는 왼쪽 끝의 숫자를 정렬이 끝났다고 가정한다.
계속해서 아직 작업이 끝나지 않은 숫자들 중에서 가장 왼쪽에 있는 숫자를 꺼내서 왼쪽에 있는 작업이 끝난 숫자과 비교한다.
왼쪽의 숫자가 크면 두개의 숫자 위치를 바꾼다.
이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때까지 반복한다.
다음의 예에서는 8 > 5 이므로 위치를 교환한다.
5가 왼쪽 끝에 도착했으므로 작업을 멈추고 완료한다.
[ 5, 8, 6, 2, 4 ] - 한번 회전
동일한 작업을 모든 숫자가 정렬을 마칠 때까지 반복한다.
[ 5, 6, 8, 2, 4 ] - 두번 회전
[ 2, 5, 6, 8, 4 ] - 세번 회전
[ 2, 4, 5, 6, 8 ] - 네번 회전
장단점
- 장점
- 안정적인 정렬방법
- 레코드 수가 적을경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬방법보다 유리할 수 있다.
- 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
- 단점
- 비교적 많은 레코드들의 이동을 포함한다.
- 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않다.
삽입정렬(insertion sort) js 코드
const insertionSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let curValue = arr[i];
let j;
for (j = i - 1; j >= 0 && arr[j] > curValue; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = curValue;
}
return arr;
};