01. 요약

  • 제자리 정렬 (추가 메모리 요구 X)
  • 손 안의 카드를 정렬하는 방법과 유사
    • 카드 게임시 새로운 카드가 들어오면, 기존의 정렬된 카드 사이의 올바른 자리에 찾아 삽입
  • 자료 배열 안에서 매 순서마다 해당 원소의 앞의 이미 정렬되어 있는 모든 요소를 차례대로 비교하여, 자신의 위치를 찾아서 삽입하는 알고리즘
  • 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로도 사용된다.

02. 원리 (작동 방식)

  • 두 번째 자료부터 시작해 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮긴 후에 지정한 자리에 자료를 삽입한다.
    • 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째와 비교한 후 삽입할 위치를 찾는다.
    • 삽입할 위치를 찾았다면, 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

03. 순서도 (알고리즘)

const InsertionSort = (array) => {
	const length = array.length;
	let key, i, j;

	for (i = 1; i < length; i++) {
		// 1. (i = 1 주의!)
		key = array[i];

		for (j = i - 1; j >= 0 && array[j] > key; j--) {
			// 2.
			array[j + 1] = array[j];
		}

		array[j + 1] = key; // 3.
	}

	return array;
};
  1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 없기 때문에, 두 번째 위치(index)부터 탐색 시작, key에 삽입될 숫자인 i번째 정수를 복사
  2. 현재 정렬된 배열은 i - 1까지이므로 i - 1번째부터 역순으로 검사해가며 key값보다 크다면 뒤(오른쪽)로 원소를 이동시킨다. (j → j+1)
  3. 삽입될 위치에 key값을 삽입한다.

04. 특징

  • 장점
    • 안정한 정렬이다.
    • 알고리즘이 단순하다.
    • 대부분의 원소가 이미 정렬되어 있다면, 매우 효율적이다.
    • Selection Sort나 Bubble Sort와 비교해 상대적 빠르다.
  • 단점
    • 비교적 많은 레코드들의 이동을 포함한다.
    • 레코드 수가 많고, 레코드 크기가 클 경우 적합하지 않다.

05. 복잡도

  • 시간 복잡도
    • 최악의 경우(역순)에는 Selection Sort와 마찬가지로 O(n^2)이다.
      • (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2
    • 최선의 경우(이미 정렬됨)에는 한 번씩 밖에 비교를 안해서 O(n)이다.
    • 최선 O(n), 평균과 최악 O(n^2)이다.
  • 공간 복잡도
    • 주어진 배열 안에서 교환(SWAP)을 통해, 정렬이 수행되므로 O(n) 이다.

06. 참고