개념

• 가장 기초적인 알고리즘
• 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식.
• 이미 정렬된 배열에서 자기 자신의 위치를 찾아 삽입된다고 하여 삽입 정렬이라고 한다.

이해

과정1

과정2

과정3 (비교 값 빼두기)

과정4 (왼쪽 값과 비교)

과정5 (크면 더이상 비교x, 삽입)

과정6 (비교 값 빼두기)

과정7 (왼쪽 값과 비교)

과정8

과정9 (더이상 비교할 값이 없으면 비교x, 삽입)

과정 10 ~ (반복)

코드

function insertSort(arr) {
	const size = arr.length;
	
	for(let i = 1; i < size; i++) {
		let current = arr[i];
		let tobeInsertedIdx = i - 1;

		while(tobeInsertedIdx >= 0 && arr[tobeInsertedIdx] > current) {
			arr[tobeInsertedIdx + 1] = arr[tobeInsertedIdx];
			tobeInsertedIdx--;
		}
		arr[tobeInsertedIdx + 1] = current;
	}
}

특징과 시간 복잡도

• 장점: 최선의 경우 O($n$)
• 단점: 요소가 너무 많으면 비교적 많은 이동을 해야하므로 성능이 좋지 않다.
• 시간 복잡도
  • 최악 : O($n^2$)
  • 평균 : O($n^2$)
  • 최선 : O($n$) (정렬이 되어있는 경우)