삽입 정렬(Insertion Sort) 이란?

삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분(정렬된 서브리스트)에

삽입하면서 정렬을 완성하는 방식이다.

마치 카드 게임에서 손에 든 카드를 정렬할 때 새로운 카드를 올바른 위치에

끼워 넣는 것과 비슷하다고 생각하면 이해가 좀 더 쉽다.

삽입 정렬은 다른 복잡한 정렬 알고리즘(Ex. 퀵 정렬, 병합 정렬)에 비해 효율성이 떨어지지만,

구현이 쉽고 특정 상황(작은 데이터, 거의 정렬된 데이터)에서는 유리할 수 있다.

동작방식

  1. 배열의 첫 번째 요소는 이미 정렬된 것으로 간주한다.(하나의 요소는 그 자체로 정렬되어 있기 때문이다.)
  2. 두 번째 요소부터 시작하여 현재 요소를 key로 지정한다.
  3. key를 정렬된 서브리스트(즉, key의 왼쪽 부분)의 요소들과 비교한다.
  4. key보다 큰 요소들을 한 칸씩 뒤로 밀어낸다.
  5. key가 들어갈 적절한 위치를 찾으면, 그 위치에 key를 삽입한다.
  6. 이 과정들을 배열의 모든 요소를 처리할 때까지 반복한다.

특징