시간복잡도
최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.
하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 된다.
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.
그림설명
- i for문 0번쨰 인덱스 부터 끝까지 탐색하며 해당 i번째 인덱스를 tmp 배열에 저장한다.
- j for문을 통해 i 바로 전 인덱스부터 0번째 인덱스까지 거꾸로 탐색한다.
- j 인덱스가 tmp보다 크면 j+1 인덱스에 j인덱스 숫자를 복사한다.
- 그렇지 않은 경우 for문을 끝내고, j+1번째에 tmp 인덱스를 복사한다.
function solution(arr) {
let answer = arr;
for ( let i = 0; i < arr.length; i++ ) {
let tmp = arr[i], j;
for ( j = i-1; j >= 0; j-- ) {
if (arr[j] > tmp ) arr[j+1] = arr[j];
else break;
}
arr[j+1] = tmp;
}
return answer;
}
let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr));장점
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort) 이다.
- Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.
단점
- 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
- Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.
Conclusion
Selection Sort와 Insertion Sort는 k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점에서 유사하다. 하지만, Selection Sort는 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 Insertion Sort는 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있다.
