Sorting

Insertion Sort

platinant 2016. 9. 19. 20:55

삽입 정렬은 앞의 두 정렬과 같이 유명한 \(\BigO{N^2}\)정렬 중 하나이다. 하지만 앞의 두 정렬과는 크게 다른 점이 있다. 앞의 두 정렬은 정렬해야 할 값들이 다 주어져야만 알고리즘을 실행할 수 있지만 삽입 정렬은 나중에 자료가 추가되어도 알고리즘을 실행할 수 있다는 것이다.

삽입 정렬은 이미 정렬된 배열에 새로운 수를 추가하고 새로 정렬된 배열을 만들어냄으로써 정렬을 한다. 새로 정렬된 배열을 만들기 위해서는 원래 배열에서 새로 들어온 수가 들어갈 위치를 찾아야 한다. 이를 위해 맨 뒤의 큰 수들부터 차례로 비교해가며 버블 정렬하듯이 두 수를 바꾸어가며 알맞은 자리를 찾아간다. 이 아이디어를 코드로 표현하면 다음과 같다.

버블 정렬에서와 마찬가지로 삽입 정렬에서도 교환 횟수를 생각해 볼 수 있는데 버블 정렬과 같이 인접한 두 수를 교환하기 때문에 교환 횟수는 동일하다.

삽입 정렬을 더 빠르게 바꾸고 싶다면 기존의 정렬된 배열에서 새로 추가된 수가 어느 위치에 들어가야 하는지를 구하고, 새로 정렬된 배열을 빠르게 얻으면 된다. 하지만 이를 구현하려고 하면 꽤 어렵다. 배열을 사용하면 위치를 이진탐색으로 빠르게 얻을 수 있지만 새로운 배열을 빨리 얻을 수 없다. 빠른 갱신을 위해 리스트를 사용하면 새로운 수가 들어갈 위치를 빠르게 찾을 수 없다. 즉, 선형 자료구조를 사용하면 이를 해결할 수 없다.

이를 위해 필요한 자료구조는 트리이다. 이분검색트리를 사용하면 새로 추가된 원소를 알맞은 자리에 넣으면서 정렬된 배열을 빠르게 갱신할 수 있다.


다음은 삽입 정렬에 관한 재미있는 문제들이다.