정의
삽입정렬은 카드 게임을 할 때 손에 든 카드를 정리하는 것처럼, 각 원소를 이미 정렬된 부분의 올바른 위치에 하나씩 꽂아 넣는 정렬 방법입니다.
핵심 특성
- ✓앞에서부터 정렬된 부분을 점점 확장 - 왼쪽은 항상 정렬됨
- ✓거의 정렬된 데이터에서 매우 빠름 - 최선의 경우 O(n)
- ✓안정 정렬 - 같은 값의 순서가 유지됨
- ✓작은 데이터에 효율적 - 간단하고 추가 메모리 불필요
활용 사례
이런 상황에서 사용됩니다:
🃏
카드 게임 정렬
게임 중 한 장씩 받은 카드를 손에서 순서대로 정리하기
📊
실시간 데이터 정렬
데이터가 하나씩 들어올 때마다 바로바로 정렬된 목록에 추가
⚡
거의 정렬된 데이터
이미 거의 정렬된 데이터를 빠르게 완전히 정렬하기
주요 연산
주요 연산들:
삽입 위치 찾기
O(n)새로운 요소가 들어갈 올바른 위치를 정렬된 부분에서 찾습니다.
삽입
O(1)요소를 정렬된 부분의 올바른 위치에 넣습니다.
복잡도
시간 복잡도
최선
O(n)
평균
O(n²)
최악
O(n²)
공간 복잡도
O(1)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기