삽입 정렬: 정렬된 앞부분에 다음 값을 끼워 넣기

삽입 정렬은 앞부분이 이미 정렬되어 있다고 보고, 그다음 값 하나가 들어갈 자리를 만듭니다. 더 큰 값들만 오른쪽으로 밀면 빈자리에 현재 값을 넣을 수 있습니다.

선수 지식: 배열 인덱스, 반복문, 변수에 값을 잠시 저장하는 방법

• 정렬된 접두 구간이 한 원소씩 늘어나는 과정을 설명합니다.
• 현재 값을 덮어쓰기 전에 보관하는 이유를 이해합니다.
• 이동 횟수와 입력의 정렬 상태를 연결합니다.

한 원소짜리 앞부분에서 시작합니다

[4, 1, 3, 2]의 첫 원소 4만 보면 이미 정렬된 구간입니다. 다음 값 1을 이 구간의 알맞은 위치에 넣는다고 생각합니다. 4가 1보다 크므로 4를 오른쪽으로 한 칸 밀고 첫 자리에 1을 넣으면 앞의 두 값은 [1, 4]가 됩니다. 뒤의 3과 2는 아직 정렬하지 않았으므로 당장 손대지 않습니다.

이제 3을 앞의 [1, 4]에 넣습니다. 오른쪽부터 보면 4는 3보다 커서 옮겨야 하지만 1은 작으므로 그대로 둡니다. 1 바로 뒤의 자리에 3을 놓으면 앞부분이 [1, 3, 4]로 늘어납니다. 매번 배열 전체를 새로 정렬하는 대신, 이미 맞는 앞부분에 값 하나만 추가하는 방식입니다.

바깥 반복문의 i는 이번에 끼울 값의 원래 위치입니다. i보다 앞의 구간은 정렬되어 있고, i부터는 아직 처리하지 않았습니다. 따라서 i는 1부터 시작하며, i가 한 칸 증가할 때마다 정렬된 구간도 한 칸 커집니다. 이 규칙을 알고 보면 반복문의 시작값과 종료값이 자연스럽게 정해집니다.

큰 값만 뒤로 밀어 현재 값의 자리를 만듭니다

마지막 삽입에서 2를 변수 key에 보관한 뒤 4를 인덱스 3으로, 3을 인덱스 2로 옮깁니다. 중간 배열이 [1, 3, 3, 4]처럼 중복되어 보여도 괜찮습니다. 아직 채우지 않은 인덱스 1을 빈자리처럼 취급하고, 원래 2는 key에 남아 있기 때문입니다. 다음 비교에서 1이 2보다 크지 않으므로 멈추고 j + 1에 2를 넣습니다.

현재 값을 저장하지 않은 채 뒤로 복사하면 원래 i 위치의 값이 큰 값으로 덮여 사라집니다. 반복문 중간의 배열만 보고 모든 값이 항상 한 번씩 들어 있어야 한다고 생각하는 대신, 배열 밖의 key와 논리적인 빈자리도 함께 보아야 합니다. 한 단계가 끝났을 때 원소들이 다시 정확히 배열에 들어옵니다.

멈춘 위치의 다음 칸이 삽입 자리입니다

안쪽 반복문은 j가 0 이상이고 a[j] > key인 동안 큰 값을 뒤로 옮깁니다. 멈추는 이유는 두 가지입니다. key보다 작거나 같은 값을 만나면 그 다음에 넣고, 앞의 모든 값이 더 커서 j가 -1이 되면 인덱스 0에 넣습니다. 두 경우 모두 a[j + 1] = key라는 같은 문장으로 처리할 수 있습니다.

배열 범위 검사 j >= 0을 앞에 둡니다. 왼쪽 끝까지 밀린 상황에서 존재하지 않는 음수 인덱스를 정렬 데이터로 비교할 필요가 없기 때문입니다. 정렬된 앞부분에서 오른쪽부터 찾으므로, 멈춘 값 앞의 원소들은 모두 그 값 이하입니다. 따라서 그보다 앞까지 key의 자리를 다시 찾을 필요가 없습니다.

같은 값일 때는 이동하지 않는 엄격한 크기 비교를 사용합니다. 나중에 들어온 값은 먼저 있던 같은 값 뒤에 놓이므로 안정 정렬입니다. 단순히 조건을 >=로 바꾸면 숫자 순서는 맞아 보일 수 있어도 같은 키의 원래 순서가 달라집니다. 정렬에서 원하는 것이 크기 순서뿐인지 원래 동률 순서도 포함하는지 구분해야 합니다.

앞으로 넘겨야 할 큰 값의 수가 작업량입니다

처음부터 정렬된 입력에서는 각 key 앞의 값이 이미 작거나 같아 바로 멈춥니다. 검증과 복사를 포함해 최선 시간은 O(n)입니다. 역순에서는 i번째 값을 넣기 위해 앞의 i개를 모두 밀어야 하므로 총 이동은 1 + 2 + … + (n – 1)이고 최악 시간은 O(n²)입니다. 거의 정렬된 배열은 앞으로 넘겨야 할 큰 값이 적어 이동량이 줄어듭니다.

평균 O(n²)이라는 표현은 임의 순서의 입력을 가정한 분석입니다. 이 예제는 빈 칸 없는 유한 숫자 배열을 복사하여 오름차순의 새 배열을 반환합니다. 빈 배열·한 원소·음수·중복은 허용하고 NaN·문자열·무한대·희소 배열은 거절합니다. key와 인덱스만 보면 보조 공간은 O(1)이지만 반환 복사본을 포함한 추가 공간은 O(n)입니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function copyFiniteNumbers(values) {
  if (!Array.isArray(values)) throw new TypeError('숫자 배열이 필요합니다.');
  for (let i = 0; i < values.length; i++) {
    if (!Object.hasOwn(values, i) || !Number.isFinite(values[i])) {
      throw new TypeError('빈 칸 없는 유한 숫자 배열이 필요합니다.');
    }
  }
  return values.slice();
}

function insertionSort(values) {
  const a = copyFiniteNumbers(values);
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}

const input = [4, 1, 3, 2];
console.log(JSON.stringify(insertionSort(input)));
console.log(JSON.stringify(input));
console.log(JSON.stringify(insertionSort([2, 2, -1])));

node javascript-insertion-sort-prefix.mjs

[1,2,3,4]
[4,1,3,2]
[-1,2,2]

비용과 적용 범위

시간: 최선 O(n), 평균·최악 O(n²)

공간: O(n)

분석 조건: 평균은 임의 순서의 입력을 기준으로 합니다. 원본을 보존하는 복사본을 포함한 공간이며, 정렬 작업 자체의 보조 공간은 O(1)입니다. 같은 값은 이동시키지 않아 안정적입니다.

직접 확인해 보기

정렬된 앞부분 [1, 4, 5]에 값 3을 삽입하려면 어떤 값들을 어떤 순서로 옮기나요?

함께 읽을 글

• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 한 값을 끼우기 위해 뒤의 값을 이동시키는 비용을 연결합니다.
• 기초 구현 패턴: 조건·정수 계산·순회·상태 갱신 — 현재 값 보관과 상태 갱신의 순서를 복습합니다.

참고 자료

• Princeton Algorithms — Elementary Sorts — 삽입 정렬의 정렬된 접두 구간, 역전 쌍에 비례한 이동과 부분 정렬 입력의 특성을 참고했습니다.