[알고리즘] 삽입 정렬(insertion sort) 란 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 삽입 정렬(insertion sort)에 대해서 포스팅해보겠습니다.

---

삽입 정렬 이란

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방식입니다.

---

EX)

바로 예시를 통해서 익혀보도록 하겠습니다.

[ 3 1 2 5 4 8 7 6 ] 배열을 삽입 정렬을 통해서 정렬해보겠습니다.

 

STEP 

1은 현재 정렬되어 있는 부분 [ 3 ] 과 비교했을 때 맨 앞으로 가야 됩니다.

따라서, [ 1 3 ] 으로 정렬이 진행됩니다.

 

STEP 2]

2는 현재 정렬되어 있는 부분 [ 1 3 ] 에서 1 과 3 사이에 위치해야 합니다.

STEP 3]

5는 현재 정렬되어 있는 부분의 맨 뒤에 위치해야 하므로 다음 STEP을 진행한다.

STEP 4]

4는 현재 정렬되어 있는 부분의 3과 5 사이에 위치해야 합니다.

STEP 5]

8은 현재 정렬되어 있는 부분이 맨 뒤에 위치하면 되므로 다음 STEP으로 넘어간다.

STEP 6]

7은 현재 정렬되어 있는 부분이 5와 8 사이에 위치해야 합니다.

STEP 7]

마지막으로 6은 5와 7 사이에 위치해야 합니다.

예시를 통해 알 수 있듯이, 삽입 정렬은 해당 원소가 삽입되어야 하는 위치로 삽입을 진행하며 정렬하는 방식입니다.

그렇다면 해당 원소가 삽입되어야하는 위치로 어떻게 삽입할 수 있을까요??

정답은 해당 원소가 원하는 위치에 도달할 때까지 계속 옆의 원소와 교환(SWAP)을 진행하는 방법입니다.

 

예를 들어, [ 2 3 4 5 1 ] 과 같이 배열이 있을 때, 1은 [ 2 3 4 5 ] 배열 맨 앞으로 가야 합니다.

따라서, 5와 SWAP하고 4와 SWAP하고 3과 SWAP하고 2와 SWAP해 원하는 위치에 도달할 수 있습니다.

---

코드 구현

void insertion_sort ( int list[], int n ){
  int temp;
  for ( int i = 1; i < n; i++ )
  {
    temp = list[i];
    int j = i - 1;
    while(j >= 0 && temp < list[j]){
    	list[j + 1] = list[j];
        j--;
    }
    list[j + 1] = temp;
  }
}

코드는 간단합니다.

i 번째 원소의 위치를 찾기 위해 i - 1 번 째 원소부터 차례대로 비교해나가며 자기 위치가 아니라면 SWAP을 진행합니다.

자기 위치를 찾았다면, while 문이 깨지고 찾은 위치 j + 1 번 째에 원소를 저장해줍니다.

---

복잡도 분석

N개의 원소가 있다고 가정하고 삽입 정렬의 복잡도를 분석해보겠습니다.

삽입 정렬은 버블 정렬, 선택 정렬과 다르게 최선의 경우, 최악의 경우 시간 복잡도가 다릅니다.

 

먼저, 최선의 경우(이미 배열이 정렬되어 있는 경우)에 대해서 생각해보겠습니다.

이미 자기 위치에 있는 원소는 옆에 있는 원소와 비교 연산 1회만 진행한 후 다음 STEP 으로 넘어가게 됩니다.

즉, 최선의 경우 N - 1 개의 원소에 대해서 비교 연산을 1번씩만 진행하면 되므로 O( N )의 복잡도를 가지게 됩니다.

 

그다음으로는 최악의 경우(배열이 역순으로 정렬되어 있는 경우)에 대해서 생각해보겠습니다.

모든 STEP마다 정렬되어 있는 배열의 모든 원소들과 비교 연산을 진행해야 하므로

총 ( N - 1 ) + ( N - 2 ) +  ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

---

안정 정렬

삽입 정렬은 '안정 정렬' 입니다. 즉, 동일한 두 원소 간의 순서가 정렬 후에 바뀌지 않습니다.

삽입 정렬 작동 원리를 생각해보면 동일한 두 원소끼리는 이미 위치가 정해져 있으므로 순서가 바뀌지 않는 것을 쉽게 이해할 수 있습니다.

 

원활한 이해를 돕기 위해 [ 5-1  2  1  5-2 ] 를 삽입 정렬을 통해서 정렬해보겠습니다.

동일한 두 원소 5를 구분하기 위해 5-1 / 5-2 로 표현했습니다.

 

정렬 전 [ 5-1  2  1  5-2 ] → [ 2  5-1  1  5-2 ] → [ 1  2  5-1  5-2 ] 

 

다음과 같이 삽입 정렬은 안정 정렬인 것을 확인할 수 있습니다.

---

이상으로 삽입 정렬 포스팅을 마치겠습니다.