삽입 정렬(Insertion Sort) 이란?
삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분(정렬된 서브리스트)에
삽입하면서 정렬을 완성하는 방식이다.
마치 카드 게임에서 손에 든 카드를 정렬할 때 새로운 카드를 올바른 위치에
끼워 넣는 것과 비슷하다고 생각하면 이해가 좀 더 쉽다.
삽입 정렬은 다른 복잡한 정렬 알고리즘(Ex. 퀵 정렬, 병합 정렬)에 비해 효율성이 떨어지지만,
구현이 쉽고 특정 상황(작은 데이터, 거의 정렬된 데이터)에서는 유리할 수 있다.
동작방식
- 배열의 첫 번째 요소는 이미 정렬된 것으로 간주한다.(하나의 요소는 그 자체로 정렬되어 있기 때문이다.)
- 두 번째 요소부터 시작하여 현재 요소를 key로 지정한다.
- key를 정렬된 서브리스트(즉, key의 왼쪽 부분)의 요소들과 비교한다.
- key보다 큰 요소들을 한 칸씩 뒤로 밀어낸다.
- key가 들어갈 적절한 위치를 찾으면, 그 위치에 key를 삽입한다.
- 이 과정들을 배열의 모든 요소를 처리할 때까지 반복한다.
특징