삽입 정렬(Insertion Sort)에 대해 알아보자

이번에는 삽입 정렬에 대해 알아보자. 삽입 정렬은 앞에서부터 하나씩 정렬해 가는 방법이다. 모든 숫자에 대해서 실행해야 하기 때문에 시간복잡도는 O(n^2)을 가진다. 느린 정렬방법이지만 구현이 쉽다는 장점이 있다. 단순 비교가 대부분이기 때문이다.

 

삽입 정렬

그림을 봐보자.

빨간색 부분이 정렬이 완료된 부분이다.

처음에는 맨 앞부분 2개만을 비교한다. 2와 7을 비교해 작은 수를 앞으로 놓는다. 그리고 다음 숫자를 보고 이전에 정렬이 완료된 부분 어디에 끼워 넣어야 하는지 보면 된다. 물론 컴퓨터는 하나씩 비교해 가며 새로운 숫자가 어디에 위치해야 하는지 찾는다. 1은 2와 7 둘보다 작기 때문에 맨 앞에 들어가야 한다. 따라서 하나씩 swap을 해서 원하는 위치로 보내던지 LinkedList라면 앞에 끼워 넣고 뒤의 인덱스를 하나씩 더해줄 수도 있다. 이렇게 숫자를 하나씩 앞의 이미 정렬된 배열 어디에 끼워 넣을지 판단하고 알맞은 위치에 넣는 것이 삽입 정렬이다.

배열 형태를 사용한다면 숫자의 개수가 많고 작은 숫자가 뒤에 있을 경우 인덱스를 미루는 작업이나 swap하는 작업의 횟수가 매우 많아질 수 있으니 주의해야 한다. 이때는 꼭 배열 형태가 필요한 것이 아니라면 LinkedList를 이용해 노드의 연결관계만 수정해 주는 것도 하나의 방법이 될 수 있다.

 

버블 정렬, 선택 정렬과 마찬가지로 시간이 오래걸리는 방법이라 많이 사용되지 않지만 원리는 이해하고 가도록 하자. 백준 2750번이 시간이 여유롭니 한번 코딩해 보고 맞는지 확인해 보자.

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기