in place 알고리즘에 대해서 간단하게 알아봅시다.

 정렬 알고리즘을 배우면서, stable 한지 그렇지 않은지는 많이 본 거 같습니다. 그런데 in-place 한지 여부도 분명 다룬 거 같았습니다. 그런데, 저는 이 부분에 대해서 잘 신경을 쓰지는 않았는데요. 쉽게 간과할 정도로 무지했던 셈입니다. 정리할 겸 겸사겸사 알아보도록 하겠습니다.

 

---

 먼저, in place 알고리즘은 추가적인 메모리를 쓰지 않는 알고리즘? 그런데 아주 약간의 메모리를 써도 되는 알고리즘 정도로 문서에서 언급하고 있어요. 제가 보는 교과서에서는 constant한 공간을 쓰면 in-place 알고리즘이라고 언급하고 있습니다만, 대충 인풋 크기에 비해 정말 작은 메모리를 쓴다. 정도로만 이해하고 넘어가셔도 좋겠네요. 대충 input size가 500만 정도라고 생각해 보면, int나 long 형 변수 하나, 둘? 한 20개? 30개 정도는 써도 괜찮겠죠? 아마 괜찮을 겁니다. 500만에 비해 20이나 30은 매우 작기 때문입니다.

 

 예를 들어서, 문자열을 역순으로 뒤집는 것을 생각해 봅시다.

 

 

 pat 배열의 맨 끝에서부터 str의 원소들을 차례대로 넣은 다음에, pat 배열의 내용을 str에 복사하는 방식의 알고리즘을 생각할 수 있어요. 그러면, 공간은 아래와 같이 써먹게 됩니다.

 

 

 기존에 있었던 데이터에 비해서 작업을 하기 위해 만들어 놓은 공간이 결코 작지는 않아요. 그런데, 사실 문자열을 뒤집는 것은 아래와 같이 해도 크게 문제가 없습니다. 양쪽 끝에서부터 서로 배열 원소를 바꿔치기 하는 로직으로 접근하면 어떨까요? 예를 들어서, 이런 배열이 있다고 해 봅시다.

 

 

 그러면 왼쪽 포인터와 오른쪽 포인터를 두고, 왼쪽 포인터를 가장 왼쪽에 있는 것을, 오른쪽 포인트를 가장 우측에 있는 것을 가리키게 합니다. 먼저 왼쪽 끝에 있는 것과 오른쪽 끝에 있는 것을 서로 맞바꿉니다. 그 다음에 left pointer는 우측으로, right pointer는 좌측으로 이동시킵니다.

 

 

 다음에 왼쪽에서 2번째에 있는 원소와 오른쪽에서 2번째에 있는 원소와 맞바꿉니다. 그 다음에 left는 우측으로, right는 좌측으로 이동시켜요.

 

 

 그러면 left는 3번째를 right는 2번째 원소를 가리킬 거니까 끝냅니다. 그러면 원래 문자열이였던 orei가 iero로 바뀌게 됩니다. 이 경우에는 배열의 크기가 4였지만, 500만개짜리 배열에 대해서도 마찬가지 방법으로 접근할 수 있어요.

 

 

 해당 방법으로 문자열을 뒤집는 것을 구현해 보았어요. i와 j를 각각 문자열의 시작점과 끝점을 잡고 루프가 돌 때 마다, i는 증가시키고, j는 감소시켰어요. 루프는 i가 j보다 작을 때 돌리게 했고요. str을 뒤집기 위해서, 추가적인 공간을 그렇게 많이 할당하지는 않았어요. 3개? 그런데 3개는 500만에 비해서 한없이 작은 수치입니다. 즉 i와 j와 swap을 위해 필요한 변수 등은 500만개의 배열에 비해 아주 약간의 메모리만 소모할 뿐입니다.

 

 

 잘 뒤집어 진 거 같네요. 사실, 전자보다 후자가 나은데요. 메모리에 복사하고, 또 복사하는. 2번 일을 한다는 이유도 있어요. 그런데, cache hit 영향도 생각보다 크게 다가옵니다. 예전에 int 배열 500만개랑 long long형 배열 500만개에 대해서 에라토스 테네스의 체를 돌릴 때 실행 시간 차이가 왜 이렇게 많이 나느냐에 대한 답을 한 적이 있는데요. cache hit, locality 등의 키워드를 찾아보시면 도움이 된다고 답변을 해 드린 적이 있었습니다.

 

 

---

 intro sort에서 자주 이용되는, 복잡도가 n^2짜리인 정렬 알고리즘인 insertion sort는 어떨까요? 이것 역시 추가적인 공간을 그리 많이 소모하지 않습니다.

 

 

 로직을 잘 생각해 봅시다. 이미 정렬된 것들은 노란색으로 표시했습니다. 그리고 현재 턴에 올바른 자리에 들어가야 할 원소는 군청색으로 표시해 두었는데요. 2가 들어갈 자리는 1과 4 사이입니다.

 

 

 그러면 노란색 뒤에, 주황색 앞에 들어가야 할 겁니다. 따라서, 주황색으로 표시된 것들을 뒤로 1칸 밀어버립니다.

 

 

 다음에 군청색으로 표시된 것이 주황색 앞에 옵니다. 이 과정은 추가적인 메모리가 필요하지 않습니다. 단지, 군청색이 어떤 원소였는지만 저장해 두고, 주황색 부분만 뒤에 있는 원소부터 1칸씩 뒤로 밀어버리기만 하면 되기 때문입니다. 배열의 크기가 500만이 되도, 끽 해봐야 현재 턴에 위치를 찾아야 할 수를 저장할 공간하고, 배열의 특정 위치를 가리키는 포인터 몇 개만 관리하면 됩니다. 이는 500만보다 한참 작은 수치입니다. 따라서 insertion sort는 in place 하다고 할 수 있어요.