정의
손안의 카드를 정렬하는 방법과 유사.
선택정렬과 유사하지만 좀더 효율적인 알고리즘이다.
삽입 정렬은 번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘이다.
최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.
코드
function insertionSort(arr) {
for (let index = 1; index < arr.length; index++) {
let temp = arr[index];
let prev = index - 1;
while (prev >= 0 && arr[prev] > temp) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = temp;
}
console.log(arr);
}
- 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
- temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
- '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.
시간복잡도
최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.
하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 된다.
언제 사용하면 좋을까?
삽입 정렬은 작은 데이터셋에 대해 효율적으로 작동하는 정렬 알고리즘이다. 데이터가 이미 정렬되어 있는 경우나, 대부분 정렬되어 있는 경우에는 퀵 정렬이나 병합 정렬 등의 다른 알고리즘이 더 효율적일 수 있지만, 입력 데이터가 거의 정렬된 상태일 경우에는 삽입 정렬이 가장 빠르다. 또한 입력 데이터가 상당히 작을 경우에도 삽입 정렬은 유용합니다. 삽입 정렬은 안정적인 정렬 알고리즘이며, 데이터가 이미 거의 정렬된 경우에는 매우 빠르게 작동한다. 따라서 작은 데이터셋이나 데이터가 이미 거의 정렬된 경우에 삽입 정렬을 사용할 수 있다.
결론적으로, 대부분의 원소가 이미 정렬되어 있거나 , 배열의 길이가 짧을때 사용하면 효율적이다.
출처
