삽입 정렬(Insertion sort)

이번 포스팅은 선택 정렬에 이어 삽입 정렬에 대해 알아보겠습니다.

삽입 정렬(insertion sort)란 

아직 정렬 되지 않은 임의의 데이터를 이미 정렬 된 부분의 적절한 위치에 삽입해가며 정렬하는 방식이다.

예를 들면 카드 게임을 할 때 이미 내 손에는 정렬 된 카드가 있다고 할 때

새로운 카드를 받아 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지 되게 하는 것이다.

1회전의 경우 첫번째 데이터는 정렬이 된 리스트라고 가정을 하고, 두번째 데이터를 기준으로 하여

앞에있는 데이터와 비교를 하여 값을 swap한다.

2회전의 경우 세번째 데이터는 앞에 있는 두번째 데이터와 비교후 자신의 데이터가 더 작으므로

그 앞의 첫번째 데이터와 한번 더 비교를 하게 된다.

첫번째 데이터와 비교후 자신의 데이터가 더 크므로 세번째 데이터는 두번째 데이터와 swap하게 된다.

이때 두번째 데이터 보다 자신의 데이터가 크게 된다면 그 앞의 첫번째 데이터와 비교 할 필요가 없다.

이러한 방식으로 좀더 간략하게 설명하자면

1. 정렬이 된 리스트의 가장 우측의 값부터 현재의 key 값과 비교를 한다.

2-1. 오름차순 기준으로 key값이 정렬 된 리스트 우측 값보다 작다면 그 앞의 값과 다시 비교를 한다.

2-2. key값이 정렬 된 리스트 우측 값보다 크다면 그 위치로 데이터가 삽입 되고

key값보다 우측에 있게 되는 정렬 된 리스트의 데이터들은 한 칸 씩 밀리게 된다.

이러한 과정을 key값을 증가시키며 key값이 더이상 존재하지 않을 때까지 반복한다.

이를 c언어 소스 코드로 나타내면 다음과 같다.

삽입 정렬의 시간 복잡도는 list의 구성이 어떻게 되어 있느냐에 따라 달라진다.

예를 들어 list가 이미 정렬 되어 있는 경우에는 외부 루프 n-1번만 실행되고 

각 단계에서 데이터의 이동 없이 1번의 비교 연산만 수행되기 때문에

이러한 최선의 경우 알고리즘의 시간 복잡도는 이다.

하지만 오름차순으로 정렬해야 하는 데이터가 역순으로 내림차순으로 정렬 되어 있다면

각 단계에서 앞에 놓인 데이터들은 전부 한 칸씩 뒤로 이동 해야하고,

외부 루프 안의 각 반복마다 i번 비교가 수행되기 때문에

이러한 최악의 경우 알고리즘의 시간 복잡도는 이다.

삽입 정렬은 비교적 정렬이 된 리스트에서는 이동 횟수가 선택 정렬과 버블 정렬에 비해 

적게 일어난다는 장점이 있다.

하지만 데이터의 수가 많고 크기가 큰 경우에는 적합하지 않다는 단점도 있다.

이상으로 삽입 정렬에 대해 알아 보았습니다.

정렬에 대해 포스팅을 시작 할 때 언급 했듯이 정렬 방법들에 대해 이해하고

주어진 환경에서 어떤 정렬 방법을 쓰느냐가 중요하다고 생각합니다.

다음 포스팅에서는 버블 정렬(Bubble sort)에 대해 알아 보겠습니다.