알고리즘SortO(n²)Adaptive

삽입 정렬

카드 패 정리하듯 원소를 적절한 위치에 삽입하는 정렬

시각화 로드 중...

알고리즘 복잡도

최선O(n)
평균O(n²)
최악O(n²)
공간O(1)
안정 정렬 ✓

개요

Algorithm Overview

삽입 정렬(Insertion Sort)은 아직 정렬되지 않은 원소를 하나씩 꺼내어 이미 정렬이 완료된 앞부분 배열의 올바른 위치를 찾아 삽입하는 정렬 알고리즘입니다.

01

손패 정렬 메커니즘

  • 키(Key) 추출: 1번 인덱스 원소부터 차례대로 현재 삽입할 타겟 key로 선택합니다.
  • 시프트(Shift) 이동: key보다 큰 좌측의 정렬된 원소들을 우측으로 한 칸씩 밀어냅니다.
  • 최적 위치 삽입: key보다 작거나 같은 원소를 만난 직후의 빈 공간에 key를 안착시킵니다.
02

적응형(Adaptive) 특성과 실무 가치

  • 거의 정렬된 배열에서 최고 속도: 데이터가 이미 대부분 정렬되어 있다면 시프트 연산 없이 $O(n)$ 시간에 정렬을 완료합니다.
  • 하이브리드 정렬의 핵심 서브루틴: $N le 32$ 수준의 소규모 구간에서는 퀵 정렬이나 병합 정렬보다 함수 호출 오버헤드가 적어 Python의 Timsort처럼 작은 실행(run)을 활용하는 하이브리드 정렬에서 구성 요소로 사용됩니다.

입력을 따라가는 실행 예제

[4, 2, 3]에서 2를 키로 잡으면 4를 한 칸 밀어 [2, 4, 3]을 만들고, 다음 키 3을 넣을 때 4를 밀어 [2, 3, 4]가 됩니다. 반대로 [2, 3, 4]에서는 원소를 옮길 필요가 없어 각 키마다 한 번의 경계 비교만 필요합니다.

학습 목표

  • 키와 정렬된 접두 구간의 경계가 어떻게 이동하는지 설명할 수 있다.

자주 하는 오해

  • 삽입 정렬은 임의의 두 원소를 교환하는 방식만 가능한 것이 아닙니다. 일반적으로 큰 원소를 오른쪽으로 밀고 키를 빈 자리에 넣습니다.

핵심 정리

  • 거의 정렬된 입력에서는 이동이 적어 효율적이지만 역순 입력에서는 이동 횟수가 제곱 규모로 증가합니다.

학습 확인

문제 1

[4, 2, 3]에서 키 2를 삽입한 직후 상태는?

핵심 단계

  1. 1

    인덱스 1부터 시작, 현재 원소(key)를 임시 저장

  2. 2

    정렬된 부분(왼쪽)에서 key보다 큰 원소들을 오른쪽으로 한 칸씩 이동

  3. 3

    빈 자리에 key 삽입

  4. 4

    인덱스를 1씩 증가하며 배열 끝까지 반복

핵심 개념 및 실무 적용 분야

✓거의 정렬된 데이터의 실시간 정렬
✓Python Timsort, Java Arrays.sort() 소규모 구간 서브루틴
✓온라인 정렬 (데이터가 하나씩 도착할 때)

참고 자료

개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.