비교
교환
패스

  • 삽입 중
  • 비교 중
  • 교환됨
  • 정렬된 부분

삽입 정렬 자세히 알아보기

삽입 정렬

삽입 정렬은 많은 사람이 손에 든 카드를 정리하는 방식과 같습니다. 목록 앞쪽에 정렬된 부분을 유지하면서 다음 값을 꺼내, 더 큰 값을 모두 지나 제자리를 찾을 때까지 앞으로 옮깁니다. 원하는 속도로 재생하거나 비교를 하나씩 진행하면서 비교, 교환, 패스 카운터를 지켜보세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 타일에는 비교, 교환, 패스 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
  3. 거의 정렬된 목록과 역순 목록을 각각 시험해 보고, 비교 횟수가 얼마나 다른지 비교해 보세요.

삽입 정렬의 원리

첫 번째 값 하나만으로 정렬된 부분이 됩니다. 두 번째 값을 꺼내 바로 앞의 값과 비교합니다. 앞의 값이 더 크면 교환하고, 앞의 값이 더 크지 않거나 값이 맨 앞에 닿을 때까지 비교와 교환을 계속합니다. 이제 처음 두 값이 순서대로입니다. 세 번째, 네 번째 값도 같은 방법으로 목록 끝까지 진행합니다.

거의 정렬된 목록에서 빠름

각 패스는 더 크지 않은 첫 값에서 멈추므로, 이미 제자리에 가까운 값은 비교 한두 번이면 됩니다. 정렬된 목록은 비교 n − 1번에 교환이 없고, 최악의 경우인 역순 목록은 비교와 교환이 각각 n(n − 1)/2번입니다. 교환 횟수는 항상 시작 목록의 역순쌍, 즉 순서가 뒤바뀐 쌍의 개수와 같습니다. 그래서 삽입 정렬은 짧거나 거의 정렬된 목록에 자주 쓰이고, 더 빠른 정렬 안에서 작은 조각을 마무리하는 데도 쓰입니다.

자주 묻는 질문

삽입 정렬은 어떻게 동작하나요?

목록 앞쪽에 정렬된 부분을 만들어 갑니다. 각 패스는 다음 값을 꺼내 앞에 있는 더 큰 값을 모두 지나 제자리에 들어갈 때까지 앞으로 옮깁니다. k번째 패스가 끝나면 처음 k + 1개 값이 순서대로지만, 나중 값이 그 사이에 끼어들 수는 있습니다.

삽입 정렬은 비교와 교환을 몇 번 하나요?

교환 횟수는 항상 시작 목록의 역순쌍 개수와 같습니다. 정렬된 목록은 0번, 역순 목록은 n(n − 1)/2번입니다. 비교 횟수는 교환 횟수에 패스마다 최대 한 번을 더한 값이므로 n − 1번에서 n(n − 1)/2번 사이입니다.

삽입 정렬은 왜 거의 정렬된 목록에서 빠른가요?

패스가 더 크지 않은 값을 만나는 즉시 멈추기 때문입니다. 모든 값이 최종 위치에 가까우면 패스가 모두 짧아서, 전체 정렬 시간이 n에 가까워집니다.

삽입 정렬은 안정 정렬인가요?

네. 값은 자신보다 엄격히 큰 값만 지나가므로, 같은 값끼리는 서로 지나치지 않고 원래 순서를 유지합니다.

입력한 숫자가 어딘가로 전송되나요?

아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동