삽입 정렬 알고리즘 : 원소가 들어갈 위치는 어디인가?

 정렬 알고리즘 시리즈를 쓰려고 합니다. 총 20 ~ 25편 정도로 구성이 될 듯 싶습니다. 먼저 O(n^2)짜리 알고리즘 3대장을 써 볼 건데요. 아마도, 알고리즘 교재에서는 맨 처음에 나올 듯 싶습니다. 오늘은 그 중, 삽입 정렬에 대해서 알아보겠습니다.

 

 이 글을 이해하기 위해서는 memcpy와 memmove를 이해하면 더없이 좋을 겁니다.

 

 

[관련글]

메모리 복사 함수는 어떻게 쓸까요?

 

 

---

 

 삽입정렬 알고리즘은 Loop를 돌면서 해당 원소가 이미 정렬된 부분 배열에서 어디로 들어가면 좋은지를 구한 다음에, 그 위치에 넣는 식으로 동작합니다. [6, 3, 4, 2, 1, 3]을 오름차순으로 정렬한다고 해 봅시다. 수가 작을수록 우선 순위가 높을 겁니다. 먼저 1회전을 돌 겁니다. 6을 선택합니다. 제가 파란색으로 칠한 부분은 정렬이 되어 있어야 하는데요. 그러면 6은 어디에 넣으면 될까요?

 

 

 

 첫 번째 자리에 넣으면 될 겁니다. 이 부분은 아무런 문제가 없어요. 그 다음에 3을 넣어봅시다.

 

 

 파란색 부분이 정렬이 되어 있어야 하는데요. 그럴려면 3은 어디에 넣어야 할까요? 6의 앞에 넣으면 좋을 듯 싶군요.

 

 

 그러면 파란색으로 칠한 부분은 sorting이 될 거에요. 다음에 4를 넣어볼 건데요. 이 친구는 3보다는 뒤에, 6보다는 앞에 와야 합니다. 그렇기 때문에, 6 앞에 넣으면 되겠습니다.

 

 

 이제 2를 넣어봅시다. 이건 어떤가요? 맨 앞에 넣으면 되겠죠. 그렇기 때문에, 3, 4, 6이 뒤로 1칸씩 밀려납니다.

 

 

 이제 1을 넣어봅시다. 2는 1보다 크기 때문에, 2 앞에 넣습니다. 그렇기 때문에 2, 3, 4, 6이 뒤로 1칸씩 밀려납니다.

 

 

 마지막으로 3을 넣을 건데요. 3보다 큰 최초의 위치는 3번째 원소입니다. arr[3]의 값이 4이기 때문입니다. 그렇기 때문에, 4와 6을 뒤로 1칸씩 밀면 됩니다. 앞에 있던 3을 노란색으로 표시했습니다.

 

 

 이 점은 꽤 중요한 정렬의 특성 중 하나입니다. 이 특성은 선택 정렬까지 이야기 하고 언급을 하겠습니다. 이것을 코드로 구현하면 다음과 같습니다.

 

 

 보시면 그렇게 복잡하지 않다는 것을 알 수 있는데요. insert를 해야 할 수를 변수 in으로 두었습니다. 그리고, 그 수가 있는 위치를 lo라고 한다면, lo-1부터 0까지 탐색해야 합니다. 만약에 arr[lo]가 in보다 크다면, arr[lo+1]에 arr[lo]를 대입해야 할 거에요. 만약에 arr[lo]가 in보다 작거나 같다면, 빠져 나오면 됩니다. arr[0]이 in보다 크다면, in이 들어갈 자리는 0번째 위치이니까, 그 처리도 해 주면 좋겠네요.

 

 

 

 물론 그 처리는, lo 변수를 하나 더 두면 깔끔하게 처리할 수 있어요. 바깥쪽 for 문을 돌 때마다, lo는 -1로 초기화 되는데요. 만약에, 안쪽 for문을 다 돌았는데도 lo가 -1이였다. 그러면, arr[0]도 lo보다는 우선 순위가 작다는 이야기이므로, 그냥 arr[0]에 lo를 넣어주면 되겠습니다.

 

 기존에 arr[0]의 값은 arr[1]로 이동했을 거니 문제 없다는 것을 알 수 있어요.

 

 

---

 삽입 정렬 알고리즘은 한 사이클에 크게 2가지 연산이 있습니다. 어떠한 수 x를 넣을 때, x보다 큰 최초의 위치 lo를 찾는 연산. 그리고 x를 insert 하기 전에, lo보다 뒤에 있는 것들을 뒤로 밀어버리는 연산.

 

 

 예를 들어, 1 3 4 20 25 5 7이 있었고, 5회전을 돌았다고 해 봅시다. 그러면 파란색 부분은 이미 정렬이 되었을 겁니다.

 

 

 이 때, 5를 넣으려면 어떻게 해야 할까요? 일단, 1, 3, 4, 20, 25는 sorting이 되어 있습니다. 즉, arr+0부터 arr+4까지 보았을 때, 5보다 큰 최초의 위치를 찾아야 하는데요. 파란 부분이 정렬이 되어 있기 때문에 이분 탐색으로 lo를 빠르게 찾을 수 있습니다. C++의 STL을 이용하신다면 upper_bound를 이용하시면 되겠습니다.

 

 

 다음에 뒤로 1칸씩 미는 건 어떻게 구현하면 될까요? 우리는 바이트 단위로 빠르게 복사하는 함수인 mem 계열 함수 2개를 배웠습니다. 그런데 original 공간, 그러니까 노란색으로 칠해진 부분하고, 복사될 공간, 연두색으로 칠해진 부분이 겹칩니다. overlap 되는 부분이 있어요. 그러면 memmove를 쓰면 좋겠지요. 보통, mem 계열은 for문을 돌면서 일일히 대입하는 연산보다는 빠르다는 것이 알려져 있습니다. 정리 하면 이분 탐색으로 빠르게 내가 넣을 위치를 찾고, mem 계열 함수로 뒤로 1칸씩 밀어버리는 연산을 구현한다면 조금 더 빠른 삽입 정렬 알고리즘을 만들 수 있습니다.