삽입정렬 시각화
요소를 하나씩 꺼내 정렬된 부분의 올바른 위치에 삽입하는 과정을 관찰합니다
정렬★☆☆
속도
1 / 1비교 횟수: 0이동 횟수: 0
배열 크기20
현재 요소비교 중이동 중정렬 완료미정렬
요소가 정렬된 부분의 올바른 위치에 삽입되는 과정을 관찰하세요.
요소가 정렬된 부분의 올바른 위치에 삽입되는 과정을 관찰하세요.
삽입정렬이란?
삽입정렬(Insertion Sort)은 카드를 정리하듯, 정렬되지 않은 부분에서 요소를 하나씩 꺼내 정렬된 부분의 올바른 위치에 삽입하는 알고리즘입니다. 소규모 데이터나 거의 정렬된 데이터에서 매우 효율적입니다.
사용 방법
- 1배열 크기를 조절하세요
- 2보라색 막대가 현재 삽입할 요소입니다
- 3주황색 막대는 오른쪽으로 밀리는 요소입니다
- 4왼쪽의 밝은 영역이 이미 정렬된 부분입니다
- 5거의 정렬된 입력에서 특히 빠른 것을 확인하세요
동작 원리
- 1두 번째 요소부터 시작하여 현재 요소를 '키'로 저장합니다
- 2왼쪽 정렬된 부분에서 키보다 큰 요소들을 오른쪽으로 한 칸씩 이동합니다
- 3빈 자리에 키를 삽입합니다
- 4마지막 요소까지 반복하면 전체 정렬이 완료됩니다
실무 활용
- •카드 게임에서 패를 정리하는 방식 그대로 — 사람이 직관적으로 사용하는 정렬입니다
- •데이터베이스의 소규모 삽입 시 정렬 상태를 유지할 때 사용됩니다
- •Python의 Timsort 내부에서 작은 부분 배열(run) 정렬에 사용됩니다
- •온라인 알고리즘 — 데이터가 하나씩 들어올 때 즉시 정렬된 위치에 삽입할 수 있습니다
비슷한 알고리즘
- •버블정렬 — 같은 O(n²)이지만 삽입정렬이 비교/이동 횟수가 적어 실무에서 선호됩니다
- •셸 정렬(Shell Sort) — 삽입정렬의 개선판. 간격(gap)을 두고 비교하여 먼 거리 이동을 줄임. O(n^1.3~1.5)
- •이진 삽입정렬 — 삽입 위치를 이진탐색으로 찾아 비교 횟수 O(n log n)이나 이동은 여전히 O(n²)
학습 팁
- •거의 정렬된 배열에서 O(n)에 가깝게 동작합니다
- •역순 배열에서 O(n²) 최악 케이스를 확인하세요
- •안정 정렬이며 제자리 정렬입니다
- •작은 배열(n<50)에서는 퀵정렬보다 빠를 수 있습니다
자주 묻는 질문
Q. 버블정렬과 차이는?
A. 삽입정렬은 이미 정렬된 부분에 삽입하는 방식이고, 버블정렬은 인접 요소를 반복 스왑합니다. 삽입정렬이 평균적으로 더 빠릅니다.
Q. 시간 복잡도는?
A. 최선 O(n), 평균·최악 O(n²). 공간 O(1).