정의
- 2번째 요소부터 마지막 요소까지 반복문을 돌면서 각각을 이전(왼쪽)요소들과 비교하여 삽입할 자리를 찾을 때까지 이전 요소들을 뒤로 밀다가 자리를 찾으면 해당 요소를 삽입하여 정렬하는 알고리즘
- 손 안의 카드를 정렬하는 방법과 유사하다
과정 (오름차순)
- 2번째 요소의 값을 temp에 저장한다
- 이전 요소와 temp의 값을 비교해 이전 요소가 더 크면 이전 요소를 뒤로 민다
- temp의 값을 이전 요소의 자리에 삽입한다
- 3번째 요소의 값을 temp에 저장하고, 마지막 요소에 다다를 때까지 과정을 반복한다
코드 (JS)
const insertionSort = (arr) => {
let temp, prev;
for (let i = 1; i < arr.length; i++) {
temp = arr[i];
prev = i - 1;
while (prev >= 0 && arr[prev] > temp) {
arr[prev + 1] = arr[prev];
prev--;
}
arr[prev + 1] = temp;
}
console.log(arr);
};시간 복잡도
- 최악, 평균: O(n^2)
- 최선: 한 번씩만 비교하므로(i.e while문을 빨리 탈출) O(n)
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해 정렬되므로 O(n)
장점
- 거품 정렬, 선택 정렬과 마찬가지로 단순하고 직관적이다
- 이미 정렬된 리스트에 자료를 하나씩 삽입/제거하는 경우 현실적으로 최고의 알고리즘
- 같은 시간 복잡도를 가지는 거품 정렬과 선택 정렬에 비해 상대적으로 빠르다
- 제자리 정렬이다.
- 안정 정렬이다.
단점
- 최악, 평균의 시간 복잡도가 O(n^2)로 비효율적이다
- 거품 정렬, 선택 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적이다
마무리
- 선택 정렬(Selection Sort)은 2차원 루프문에서 최소값을 가지는 요소를 찾기 위해 나머지 모든 요소를 순회하지만
삽입 정렬(Insertion Sort)은 while문을 활용하여 삽입할 자리를 찾으면 루프를 탈출하여 필요한 만큼의 요소만 탐색하기에 훨씬 효율적으로 실행된다는 차이가 있다
참조
Maker를 지향하는 웹 개발자입니다.