[실전 알고리즘] 0x0E강 - 정렬 I

안녕하세요, 이번 시간에는 정렬을 해보려고 합니다. 정렬이라고 하면 그냥 대충 sort 함수를 가져다 쓰면 뚝딱하고 되는거 아니냐라고 생각하실 수 있는데, 사실 틀린 말은 아닙니다. 코딩테스트의 통과만 생각하면 머지 소트니 퀵 소트니 하는게 뭐가 중요하겠습니까. 똑똑한 사람들이 이미 STL 안에 만들어놓은 함수를 그냥 가져다 쓰면 끝이죠. 그래서 지금 코딩테스트가 일주일 밖에 안남았다, 나는 다 필요없고 코딩테스트만 통과하면 땡이다 하시는 분들은 바로 0x0F강의 STL sort와 정렬의 응용 이 두 챕터만 확인하시면 됩니다.

 

그런데 그래도 명색이 코딩으로 먹고 살 예정인 우리가 머지 소트 퀵 소트 이런걸 모른다하면 조금 그렇다고 생각합니다. 또 면접에서 정말 단골 질문으로 등장하는 내용이기도 해서 시간이 엄청 촉박한게 아니라면 이번 기회에 한 번 제대로 다루고 가면 좋겠습니다.

 

사실 정렬의 종류가 진짜 많습니다. 위키피디아에 Sorting algorithm이라는 문서를 보면 거의 30개 가까이 있습니다. 하지만 이 강의에서는 당연히 모든 정렬 알고리즘을 다 다루지는 않을거고 학부 강의에서 소개할법한 몇 개만 다룹니다.

 

맨 처음으로는 기초적인 정렬 알고리즘을 다루려고 합니다. 강의를 지금까지 잘 따라올 정도의 구현력을 갖춘 분이라면 기초적인 정렬 알고리즘은 아무런 어려움없이 구현할 수 있을 것 같습니다. 그래도 설명을 해보자면 잠깐 코드는 머릿속에서 잊고 지금 이렇게 책꽂이에 책이 중구난방으로 꽂혀있는데 크기순으로 재배열을 하고 싶다고 하겠습니다. 눈앞에 책꽂이가 있다 생각하고 아이디어를 내보겠습니다.

 

저뿐만 아니라 여러분들도, 아니면 초등학생을 데려오거나 아예 어르신을 데려와도 다 똑같이 할 것 같습니다. 이렇게 제일 큰 것부터 제자리로 보내거나 제일 작은 것부터 보낼 것입니다. 그리고 이 과정의 시간복잡도는 맨 처음에 N개에서 제일 큰 원소를 찾아야 하고, 그 다음은 N-1개에서, 그 다음은 N-2개에서, … 이렇게 이어질테니 계산해보면 O(N²)임을 알 수 있습니다.

 

앞에서 본 방법을 실제 배열에 대해 적용해보겠습니다. 앞과 비슷하게 제일 끝부터 가장 큰 원소가 오게끔 하면 되고 0부터 i까지의 수 중에 가장 큰 것의 인덱스를 mxidx에 담은 후 arr[mxidx]와 arr[i]를 swap해서 해결했습니다. 그리고 이걸 STL을 이용해 드라마틱하게 코드의 길이를 줄일 수 있는데 이렇게 max_element 함수를 이용하면 됩니다.

 

max_element(arr, arr+k)는 arr[0], arr[1], arr[2], …, arr[k-1]에서 최댓값인 원소의 주소를 반환해주는 함수입니다. arr[k]까지가 아니라 arr[k-1]까지라는걸 주의하셔야 합니다. 아무튼 그러면 max_element(arr, arr+i+1)은 arr[0], arr[1], …, arr[i] 중에 최댓값인 곳의 주소를 반환하니 처음 코드에서 mxidx를 찾기 위해 for문을 돌리는 것과 똑같은 역할을 합니다. 만약 max_element를 이용해 전체 배열에서 가장 큰 원소가 들어있는 인덱스를 알고 싶다고 하면 k = max_element(arr, arr+n) - arr 라고 둬서 구할 수 있습니다.

 

max_element(arr, arr+n)도 포인터고 arr도 포인터이니 포인터끼리 빼서 인덱스를 구하는 방식인데 포인터를 정확하게 알고있지 않다면 좀 헷갈릴수도 있습니다. 잘 이해가 가지 않으면 굳이 근본적인 원리를 이해하려고 할 필요 없이 그냥 인덱스를 저런 방식으로 계산 가능하구나 정도로만 생각하고 넘어가면 됩니다.

 

지금 이 방식은 선택 정렬이라는 이름이 붙어있긴 하지만 이름이 크게 중요하지는 않아보입니다. 그리고 max_element 함수는 범위 내의 원소를 다 살펴보는 함수이기 때문에 무심코 보면 밑의 코드가 O(N)에 동작하는게 아닌가 하는 착각을 할 수 있는데 그렇지 않고 O(N²)이라는 점을 인지하셔야 합니다.

 

그리고 사실 가장 구현하기 편한건 버블 정렬입니다. 앞에서부터 인접한 두 원소를 보면서 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복하면 자연스럽게 제일 큰 것부터 오른쪽에 쌓이게 됩니다. 과정을 같이 살펴보겠습니다.

 

먼저 2와 13을 비교해보면 2가 13보다 작으니 자리를 바꾸지 않고 그대로 둡니다.

 

다음은 13과 6이고 13이 6보다 크니 둘의 자리를 바꿉니다.

 

그 다음인 13과 4도 자리를 바꿉니다.

 

그 다음 13과 -2를 보면 여기도 바꿔야 합니다.

 

이렇게 끝까지 한 번 가고나면 적어도 제일 큰 원소가 가장 오른쪽에 있다는건 확신할 수 있습니다. 과정을 보면 제일 큰 원소는 계속 뒤의 원소와 자리를 바꾸다가 가장 오른쪽에 도달하게 되기 때문입니다. 다음부터는 설명 없이 쭉 이어서 보여드리겠습니다.

 

구현 코드를 같이 보겠습니다.

 

크게 설명이 필요한 부분은 없을 것 같고, 04번째 줄에서 j가 n-1-i 미만일 때 까지 진행하는데 저걸 그냥 n-1 미만으로 두어도 코드는 잘 동작합니다. 왜 그런지는 조금만 고민해보면 금방 알 수 있기 때문에 더 이상의 자세한 설명은 생략하겠습니다.

 

앞에서 소개한 선택 정렬이나 지금 본 버블 정렬은 모두 O(N²)의 시간복잡도가 필요합니다. 이외에도 삽입 정렬이란게 존재하고 삽입, 선택, 버블 정렬 이 3개가 O(N²)에 동작하는 대표적인 정렬 방법이입니다. 그런데 앞으로 면접에서 이 3개를 구분하는걸 물어볼 일이 절대 없다고 장담할 수는 없지만 한 99.9999%로는 확신합니다. 저도 이 3개 각각이 정확히 어떤 알고리즘인지는 이번 강의를 만들면서 알았지 그 전에는 구태여 알려고 한 적이 없었습니다. 그러니 삽입, 선택, 버블 정렬 같은걸 외운다고 시간낭비할 필요는 없습니다. 다만 버블 정렬 정도는 구현할 수 있어야 할 것 같은데 그건 다들 자신 있으리라고 믿습니다. 아무튼 저희는 정렬을 O(N²)에 수행할 수 있지만 N이 커지면 O(N²)이 아무래도 좀 별로입니다. 그래서 정렬을 더 빠르게 수행할 수 있는 알고리즘들을 알아보겠습니다.

 

Merge Sort는 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법입니다. 갑분재귀가 나와서 당황하셨을 수도 있는데 이미 저희가 재귀는 지겹도록 많이 다뤘기 때문에 잘 이해할 수 있을거라고 믿습니다. 이 알고리즘은 놀랍게도 O(NlgN)에 동작합니다. N이 한 10만정도 된다고 할 때 O(N²) 알고리즘은 컴퓨터 성능에 따라 한 10초에서 1분 정도의 시간을 필요로 합니다. 그런데 O(NlgN) 알고리즘이면 사실상 눈 감았다가 다시 뜨기도 전에 연산이 다 끝납니다. N이 커지면 커질수록 이 격차는 더 커집니다.

 

Merge Sort를 하기 위해서는 먼저 길이가 N, M인 두 정렬된 리스트를 합쳐서 길이 N+M의 정렬된 리스트를 만드는 방법을 알아야 합니다. 가장 직관적으로 떠오르는 방법은 그냥 {-9, 1, 6, 8, 12, -7, 7, 13, 15}에서 버블 정렬과 같은 방법을 사용하는건데 그렇게 되면 시간복잡도는 O((N+M)²)가 됩니다. 그런데 이것보다 훨씬 더 빠르게 할 수 있는 방법이 있습니다. 그 방법을 알아차리기 위해서는 딱 하나만 생각을 해보면 됩니다.

 

여기서 제일 앞에 와야하는 수는 무엇일지 생각해봅시다. 제일 앞의 원소란건 전체 중에 가장 작은 원소란건데 가장 작은 원소를 찾기 위해서 N+M개의 모든 원소를 다 봐야할까요? 잘 생각해보면 그렇지가 않습니다. 두 리스트 각각에서 가장 작은 원소인 -9와 -7만 비교하면 끝입니다. 빨간 리스트의 나머지 원소는 -9 이상일테니 볼 필요가 없고 파란 리스트의 나머지 원소도 -7 이상일테니 마찬가지입니다. 그래서 -9와 -7을 비교해보면 -9가 제일 작으니 제일 앞에는 -9가 오게 된다는걸 O(N+M)이 아니라 O(1)에 알 수 있습니다.

 

그럼 -9 다음에 오는 수는 어떻게 알아낼 수 있을까요? 관찰력이 좋은 분이라면 1과 -7만 비교하면 된다는게 보일거고 각 리스트에서 앞으로도 쓰인 수는 빼고 나머지 중에서 가장 앞에 있는 것만 계속 채워넣으면 된다는걸 알 수 있습니다.

 

이런 식으로 처리할 수 있습니다. 이 방법을 생각해보면 저희는 비교 1번당 한 개의 원소를 제자리에 보낼 수 있으니까 길이가 N, M인 두 정렬된 리스트를 합치는건 O(N+M)에 수행 가능합니다. 이 합치는 알고리즘을 머리로 이해한 것과는 별개로 실제 구현을 시도해보면 생각보다 깔끔하게 짜는게 힘듭니다. 인덱스를 잘못 둬서 런타임 에러가 나기도 합니다.

 

아직은 감이 잘 안오겠지만 이 연산이 머지 소트의 알파이자 오메가인 관계로 실제 구현을 해보겠습니다. 충분히 도전한 이후에 제 코드를 확인해주세요.

 

 생각보다 코드가 훨씬 단순합니다. 사실 문제의 상황만 놓고 보면 굳이 배열에 합친 리스트를 둘 필요도 없고 매 순간마다 바로 출력을 해도 되긴 하지만 머지 소트를 구현할 때에는 두 리스트를 합친 결과를 어딘가에 저장할 필요가 있어서 배열 c를 사용했습니다. (코드 링크) (문제 링크)

 

결국 가장 핵심적인 부분은 14번째 줄부터 19번째 줄의 과정입니다. bidx가 m이거나 aidx가 n일 때에 대한 처리를 잘 해주셔야 하고 그 외에는 큰 문제가 없을 것 같습니다. 다만 이제 실제 제출을 했더니 런타임에러나 틀렸다는 판정을 받으신 분들이 여럿 계실 것 같은데, 제가 한 분 한 분의 코드를 다 볼 수는 없지만 대충 짐작가는 상황이 있습니다.

 

지금 14번째 줄부터 19번째 줄의 코드를 이렇게 바꾸면 어떤 문제가 있을지 고민해봅시다. 사실 대놓고 예제부터 잘못 나와서 이렇게 제출을 시도할 일은 없겠지만 딱 봤을땐 뭐가 잘못됐는지 잘 안보일 것 같습니다. aidx가 n이거나 a[aidx] > b[bidx]일 때 b의 가장 앞 원소를 c로 보내면 되는게 맞을텐데 코드가 뭐가 잘못된걸까요? 뭐가 잘못된거냐면 bidx == m인 경우를 고려하지 않았습니다.. aidx == n인지만 확인했기 때문에 b[m]이라는 잘못된 원소에 접근을 해서 이상한 값을 읽어와 런타임 에러가 나거나 이상한 값이 c에 기록될 수 있습니다.

 

처음 짜려고 시도해봤다면 굉장히 비효율적이고 긴 길이의 코드를 짰을 가능성이 큰데 그렇다고 하더라도 본인의 코드로 이 문제를 맞은 다음에 넘어가보면 좋겠습니다. 그리고 17번째 줄을 보시면 a[aidx] <= b[bidx]일 때 a의 원소를 c에 담죠. 그런데 이걸 a[aidx] < b[bidx]로 변경하면 어떤 상황이 펼쳐질까요? 이렇게 변경을 한다면 a[aidx] = b[bidx]일 때 a[aidx] 대신 b[bidx]가 c에 들어갑니다. 직관적으로 생각했을 때 a[aidx]가 들어가든 b[bidx]가 들어가든 아무 상관이 없을거고 실제로 17번째 줄이 a[aidx] < b[bidx]로 변경되어도 정렬은 잘 수행됩니다. 그런데 조금 있다가 다루겠지만 머지 소트에는 Stable Sort라는 또 다른 성질이 있고 그 성질을 만족시키기 위해서는 가능하면 둘의 크기가 같을 때 앞쪽의 원소, 즉 a[aidx]가 c에 들어가야 합니다. 조금 있다가 Stable Sort에 대해 설명할 때 지금 다룬 이 내용을 기억하고 있어주세요.

 

우리는 이렇게 두 정렬된 리스트를 선형 시간에 합칠 수 있게 되었습니다. 그리고 이제 머지 소트를 이해하기 위한 모든 준비가 끝났습니다.

 

머지 소트는 3단계로 요약이 가능한데 1번, 주어진 리스트를 2개로 나눈다. 2번, 나눈 리스트 2개를 정렬한다. 3번, 정렬된 두 리스트를 합친다. 이게 끝입니다. 여기서 예상되는 질문 1가지는 "아니 그러면 나눈 리스트 2개는 어떤식으로 정렬하는거야?" 라는건데 그렇죠? {6, -8, 1, 12}를 {-8, 1, 6, 12}로 어떻게 정렬하는걸까요? 이걸 이해하려면 다시 재귀로 가야합니다.

 

이쯤되면 거의 뇌절이긴 한데 도미노 얘기를 다시 하겠습니다. 저는 1번 도미노가 쓰러지면 언젠가는 100번 도미노도 쓰러진다는걸 여러분에게 납득시키고 싶습니다. 그래서 저는 이렇게 설명을 합니다.

 

"나는 일단 1번 도미노를 쓰러트릴거다. 그리고 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. 그렇기 때문에 100번 도미노도 쓰러진다." 이렇게 설명을 했을 때 누군가는 손을 들고 질문을 하겠죠. "100번 도미노가 쓰러지려면 99번 도미노가 쓰러져야 하는데 99번 도미노가 쓰러진다는걸 어떻게 보일건가요?" 이 질문에 대한 대답을 알아낸 사람은 {6, -8, 1, 12}를 {-8, 1, 6, 12}로 어떻게 정렬하냐는 질문도 대답할 수 있습니다.

 

100번 도미노가 쓰러지려면 99번 도미노가 쓰러져야 하고, 99번 도미노가 쓰러지려면 98번 도미노가 쓰러져야 하고, 이렇게 쭉 가다가 2번 도미노가 쓰러지려면 1번 도미노가 쓰러져야 하는데 1번 도미노는 확실히 쓰러지는게 맞으니까 결국 100번 도미노도 쓰러지게 되어있다는 설명을 할 수 있는 것 처럼 길이가 8인 리스트를 정렬하려면 길이가 4인 리스트를 정렬할 수 있어야 하고, 길이가 4인 리스트를 정렬하려면 길이가 2인 리스트를 정렬할 수 있어야 하고, 길이가 2인 리스트를 정렬하면 길이가 1인 리스트를 정렬할 수 있어야 하는데 길이가 1인 리스트는 아주 쉽게 정렬할 수 있으니 결국 우리는 {6, -8, 1, 12, 8, 15, 7, -7}을 정렬할 수 있습니다.

 

지금 이 설명이 도저히 이해가 안간다 하시면 그럴 수 있습니다. 너무 괴로워하지 마시고 일단 이해를 포기한 채로 이어서 진행한 후에 한 이틀정도 있다가 다시 곰곰히 생각을 해보면 머리가 정리되서 지금보다 더 괜찮을 것입니다. 혹시 이해에 조금이나마 도움이 될까 해서 머지 소트가 실제로 어떤 방식으로 진행되는지 그림을 보여드릴테니 한 번 참고하도록 합시다.

 

실제 구현을 다루기 전에 머지 소트의 시간복잡도를 먼저 분석해보겠습니다.

 

이렇게 전체 과정을 살펴보면 리스트가 분할하는 과정과 합쳐나가는 과정으로 구분할 수 있습니다. 비록 그림에서는 원소가 8개일 때를 예시로 들었지만 길이가 N = 2^k라고 생각하면 됩니다.

 

먼저 분할하는 부분은 나중에 코드를 보면 특별한 연산을 하는건 아닙니다. 그냥 함수 호출을 통해 관념적으로 분할되었다고 생각하는거고, 함수 호출의 횟수는 각 줄별로 1, 2, 4, …, 2^k번입니다. 이 횟수는 각 줄에 리스트가 몇 개 있는지 보면 됩니다. 예를 들어 3번째 줄을 보면 리스트가 {6, -8}, {1, 12}, {8, 15} {7, -7} 총 4개 있고 각각에 대해 함수가 호출될테니 그 줄에서 함수는 4번 호출됩니다. 그러면 분할하는 과정에서 함수호출은 1+2+4+ … +2^k = 2N - 1 = O(N)번 발생합니다. 즉 분할하는 과정의 시간복잡도는 O(N)입니다.

 

그 다음으로 합쳐나가는 과정의 시간복잡도를 알아보겠습니다. 합쳐나갈 땐 각 줄에서 모두 N번의 연산이 필요합니다. 앞에서 길이가 A, B인 두 정렬된 리스트를 O(A+B)에 구하는 방법을 같이 살펴봤습니다. 그러면 각 줄에서 둘씩 짝지어 합쳐서 다음 단계로 넘어가기 위해서는 그냥 전체 원소의 갯수만큼 필요하다는 것을 알 수 있습니다. 예를 들어 지금 이 줄과 같이 길이가 N/4인 4개의 정렬된 리스트를 둘씩 짝지어 합치는 상황이라면 필요한 연산의 횟수는 N/4 + N/4 + N/4 + N/4 = N이 됩니다.

 

그리고 분할이 완료됐을 때 리스트의 원소는 1개였다가 2^k개가 될 때 까지 매번 2배씩 커지니까 줄은 k개입니다. 그렇기 때문에 합쳐나가는 과정은 O(Nk) = O(NlgN)입니다. 분할하는 과정은 O(N)이고 합쳐나가는 과정은 O(NlgN)인데 O(N)보다 O(NlgN)이 더 크기 때문에 최종적으로 머지 소트는 O(NlgN)의 시간복잡도를 가집니다.

 

이제 이론적인건 다 했고 구현만 하면 끝입니다. 사실 아예 아무 도움 없이 직접 머지 소트를 구현해보려고 한다면 좋은 연습이 되겠지만 제가 봤을 때 이전에 머지 소트를 짜본 적이 없다면 열에 아홉도 아니고 100명중 한 99명 정도는 아예 기본적인 함수 형태 자체를 못잡아낼 것입니다. 그래서 제가 미리 기본 틀을 드릴테니 틀을 보고 나머지 부분을 완성해보도록 하겠습니다. (기본 틀 링크)

 

이걸 보고도 감이 잘 안올텐데 링크에 들어가면 주석이 달려있습니다. 들어가서 보셔도 되고 설명을 좀 하자면 merge 함수는 arr[st:en]을 정렬하는 함수입니다. arr[st:en]이라는 표현은 파이썬의 slicing 문법인데 예를 들어 arr[2:5]라고 하면 arr[2], arr[3], arr[4]까지를 말합니다. 즉 왼쪽 구간은 포함이고 오른쪽 구간은 제외입니다. arr[st:en]은 arr[st], arr[st+1], …, arr[en-1] 까지인걸 잘 이해하셔야 합니다.

 

다시 merge 함수를 얘기하겠습니다. merge 함수는 arr[st:en]을 정렬할 함수인데 여기 조건이 하나 있습니다. mid = (st+en)/2 라고 할 때 arr[st:mid]와 arr[mid:en]은 정렬되어있을 때 arr[st:en]을 정렬하는 함수입니다. 이 말은 곧 앞에서 본 2개의 정렬된 배열을 합치는걸 구현하는 함수라는 의미입니다.

 

그리고 merge_sort 함수는 그냥 arr[st:en]을 정렬하는 함수입니다. 이 상황을 이해하고 나면 지금 이 코드가 앞 슬라이드에서 본 상황을 충실하게 따라가고 있다는걸 알 수 있습니다. 13번째 줄에서의 base condition은 알아서 처리를 하시고, 15, 16번째 줄에서 주어진 리스트를 2개로 나누고 각각 정렬합니다. 그 다음으로 17번째 줄에서 나눈 두 리스트를 합칩니다. 이제 설명은 다 됐고 구현을 해봅시다. 다 한다음에 실제 정렬이 잘 됐는지 확인해보면 됩니다. 다음 슬라이드에 바로 정답 코드가 나오니까 다 짜고 나서 넘어옵시다.

 

일단 코드를 음미하는 시간을 잠깐 가지겠습니다. (코드) 맨 처음 틀을 보고서는 tmp 변수가 왜 있는건가 궁금했을수도 있는데 직접 짜다보면 금방 필요성을 알아차렸을 것입니다. merge 함수에서 두 리스트를 합친 결과를 임시로 들고있을 곳이 필요하고 이런 목적으로 사용할 리스트를 매번 새로 만들 필요 없이 그냥 전역에 하나 두면 됩니다. 또 인덱스를 고민할 필요 없이 그냥 tmp[st:en]을 바로 이용하면 됩니다.

 

서로 다른 두 배열 a, b를 합치는게 아니라 arr[st:mid], arr[mid:en]을 합친다는 차이가 있긴 하지만 코드 자체는 크게 달라지는게 없습니다. merge 함수는 그렇게 건너뛰고 merge_sort 함수에서 base condition은 그냥 배열의 크기가 1일 때입니다. 1이면 아무것도 안해도 알아서 정렬이 완료됩니다. 이후에는 그냥 재귀적으로 절반을 나눠 각각이 정렬되게 하고 merge 함수를 통해 정렬된 두 리스트를 합칩니다.

 

제가 이 재귀적인 구조에 대해 굉장히 긴 시간을 들여 설명을 했는데 그 설명을 이해했으면 설령 코드를 짜는데에는 실패했어도 지금 이 코드를 보면 동작 방식이 머리 속으로 잘 그려질 것입니다. 그런데 아직 헷갈리고 아직 이 정렬이 어떻게 수행되는건지 잘 모르겠다 하면 앞에서도 말했지만 괜찮습니다. 굉장히 어려운 내용인게 맞고 또 시간이 해결해줄 문제이니까 일단 계속 가면 됩니다. 구현한 정렬이 실제 정렬을 잘 수행하는지 확인하고 싶으면 BOJ 2751번: 수 정렬하기 2 문제에 제출해보면 됩니다. 제 코드는 2751.cpp에서 확인할 수 있습니다.

 

이렇게 코드를 잘 봤는데, 앞에서 잠깐 얘기했던 Stable Sort라는 성질이 어떤 것을 말하는건지 짚고 넘어가겠습니다. 사실 우리가 그냥 문제를 풀 때는 맨날 정수 쪼가리만 가지고 정렬을 하니까 이 부분에 대해서 생각할 일이 별로 없는데 면접때 나의 지식을 뽐낼 수 있는 기회이기 때문에 잘 보고 가셔야 합니다.

 

지금 이 사람들을 나이 순으로 정렬하는 상황을 생각해봅시다. 편의상 상의 색깔로 사람을 지칭하면 지금 파랑, 빨강, 초록은 나이가 21살로 다 똑같고 검정만 혼자 38살입니다. 그래서 나이 순으로 정렬을 한다치면 이 세 가지가 모두 올바른 정렬입니다. 이렇게 우선 순위가 같은 원소가 여러 개일 땐 정렬한 결과가 유일하지 않을 수 있습니다. 그런데 그 중에서 우선 순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬이 Stable Sort입니다.

 

즉 정렬 전에 나이가 21살로 같은 사람들의 순서가 파랑, 빨강, 초록 순이니 정렬 후에도 이 순서는 같게 두는 것입니다. 그림에서의 첫 번째로 무조건 정렬이 되는 정렬 방법은 Stable Sort이고, 첫 번째로 무조건 정렬이 된다고 보장할 수 없고 두 번째나 세 번째로 정렬이 될 수도 있는 정렬 방법은 Unstable Sort입니다. 머지 소트는 Stable Sort인데 이 성질을 만족시키려면 앞에서 본 것 처럼 앞 리스트에서 현재 보는 원소와 뒤 리스트에서 현재 보는 원소의 우선 순위가 같을 때 앞 리스트의 원소를 먼저 보내줘야 합니다. 이 부분은 우리가 코드로 구현할 때 자연스럽게 처리를 했습니다.

 

이 Stable Sort를 응용할 수 있는 몇 가지 상황들이 있는데, 첫 번째로 파일들을 정렬하는 상황을 생각해보겠습니다. 첫 번째로 파일들이 이렇게 미리 시간의 오름차순으로 나열되어 있을 때 파일을 크기 순으로, 크기가 동일하다면 빨리 생성된 순으로 정렬하고 싶다고 해봅시다. 이 때 머지 소트가 Stable Sort라는걸 기억하고 있다면 시간을 신경쓰지 말고 그냥 파일의 크기를 기준 삼아서 머지 소트를 수행해서 파일을 크기 순으로, 크기가 동일하다면 빨리 생성된 순으로 정렬할 수 있습니다.

 

또 2차원 좌표들을 x가 작은 순으로, x가 동일하다면 y가 작은 순으로 정렬하고 싶다고 하면 먼저 y의 크기를 기준 삼아서 머지 소트를 수행하고 다음으로 x의 크기를 기준 삼아서 머지 소트를 수행해서 해결할 수 있습니다. 이렇게 하면 Stable Sort의 성질 덕분에 일단 x가 작은게 앞으로 올거고 x가 같다면 x에 대해 정렬을 수행하기 전에 앞에 있었을 원소, 즉 y가 작은 원소가 앞에 옵니다.

 

다만 2차원 좌표의 정렬은 사실 이렇게 머지 소트를 두 번 수행하는 것 보다는 애초에 머지 소트를 한 번만 해서 정렬하는게 훨씬 낫고, 이렇게 하기 위해서는 정렬된 두 배열을 합치는 merge 함수에서 a[aidx]와 b[bidx]를 비교하는 부분만 살짝 바꿔주면 됩니다. 이 예제는 Stable Sort의 성질을 이렇게 이용할 수도 있겠구나 하는 정도로만 이해하시면 됩니다.

 

머지 소트 다음으로는 퀵 소트를 보겠습니다. 이름에서 볼 수 있듯 일반적으로는 퀵 소트가 거의 모든 정렬 알고리즘보다 빨라서 각종 라이브러리의 정렬은 대부분 퀵 소트를 바탕으로 만들어져 있습니다. 그런데 너무 중요한 내용이라 퀵 소트의 본 내용에 들어가기도 전에 미리 말씀을 드립니다. 코딩테스트에서 STL을 못 쓰고 직접 정렬을 구현해야 하면 절대절대절대절대절대절대 퀵 소트 쓰지 마시고 머지 소트를 쓰셔야 합니다. 이번 강의에서는 다루지 않지만 나중에 힙이라는 자료 구조를 배우고 나면 쓸 수 있는 힙 소트를 써도 되고 말고도 다른 O(NlgN) 정렬을 사용해도 되는데 퀵 소트 만큼은 절대 쓰면 안됩니다. 물론 그렇다고 해서 퀵 소트가 알 필요 없다는건 아니니까 뭐야 이거 쓸데없는건가봐 하고 건너뛰어도 안됩니다.

 

그럼 이제 본론으로 들어가서 퀵 소트가 무엇이냐 보면, 퀵 소트도 머지 소트처럼 재귀적으로 구현되는 정렬입니다. 퀵 소트에서는 매 단계마다 pivot이라고 이름 붙은 원소 하나를 제자리로 보내는 작업을 반복합니다. 지금 이 리스트를 보시면 이 원소들 사이에서 pivot은 마음대로 잡으면 되지만 편의상 제일 앞의 원소인 6을 pivot으로 잡겠습니다. 혹시 6이 아닌 다른 원소를 pivot으로 잡고 싶다고 하면 그냥 6과 자리를 바꾸기만 하면 되기 때문에 pivot은 늘 가장 왼쪽에 위치한다고 생각할 수 있습니다.

 

우리는 여기서 어떻게든 pivot을 제자리로 보내고 싶습니다. pivot을 제자리로 보낸다는 의미는 지금 그림과 같이 pivot을 올바른 자리에 넣고 pivot의 왼쪽은 pivot보다 작은 원소가, 오른쪽에는 pivot보다 큰 원소가 오게끔 하겠다는 의미입니다. 보면 비록 정렬이 되지는 않았지만 6의 왼쪽에는 6보다 작은 원소만 위치하고 오른쪽에는 6보다 큰 원소만 위치하고 있습니다.

 

pivot을 제자리로 보내고 나면 왼쪽 구간과 오른쪽 구간을 따로따로 정렬하면 되고 각 구간은 머지 소트에서 하던 짓 처럼 재귀적으로 생각하면 됩니다. 왼쪽 구간과 오른쪽 구간을 어떻게 따로따로 정렬하는건가요? 라고 여쭤보신다면 머지 소트에서의 상황이랑 동일합니다. 그 때도 리스트를 절반으로 쪼갠다 치면 각각은 어떻게 정렬하나요? 라는 질문에 대해서 논의를 했습니다. 마찬가지로 이건 결국 재귀를 잘 받아들인다면 쉽게 해결할 수 있는 의문입니다. 결론적으로 말하면 나눠진 각 리스트에서도 똑같은 짓을 하고 리스트 크기가 1 이하가 되면 base condition에 도달합니다.

 

딱 떠오르는대로 바로 구현을 하려고 한다면 pivot을 제자리로 보내는건 굉장히 쉽습니다. 임시 배열 tmp를 만들고 pivot을 제외한 나머지 원소들을 순회하면서 먼저 pivot 이하인 값들을 다 tmp에 넣습니다. 그 다음엔 pivot을 담고 다시 한 번 순회하면서 pivot 초과인 값들을 tmp에 넣습니다. 마지막으로 tmp를 원래 배열에 덮어쓰면 끝입니다.

 

코드로 구현하는 것도 어렵지 않습니다. 이 코드는 리스트의 전체 순회를 2번 하니 O(N)에 동작하고 실제로 이 코드를 재귀적으로 고쳐서 퀵 소트를 만들면 잘 동작합니다. 그런데 이렇게 구현하면 퀵 소트의 장점을 모두 뭉개버리는 짓입니다. 그래서 이렇게 구현을 하면 안됩니다.

 

퀵 소트의 장점은 추가적인 공간이 필요하지 않다는 점에 있습니다. 또 그렇게 그 배열 안에서의 자리 바꿈만으로 처리가 되기 때문에 cache hit rate가 높아서 속도가 빠르다는 장점도 따라옵니다. 그렇기 때문에 우리는 추가적인 공간을 사용하지 않고 pivot을 제자리로 보낼 방법을 고민해야 합니다. 참고로 이렇게 추가적인 공간을 사용하지 않는 정렬을 In-Place Sort라고 부릅니다.

 

앞에서 본 방법과 같이 추가적인 공간을 쓰지 않으려면 원소의 위치를 서로 잘 바꿔주면 됩니다. 그 방법은 바로 양쪽 끝에 포인터 2개를 두고 적절하게 스왑을 해주는 방법입니다.

 

우선 l, r이라고 이름 붙은 포인터 2개를 두겠습니다. l은 pivot보다 큰 값이 나올 때 까지 오른쪽으로 이동하고 r은 pivot보다 작거나 같은 값이 나올 때 까지 왼쪽으로 이동합니다. 그 다음 두 포인터가 가리키는 원소의 값을 스왑합니다. 이걸 l과 r이 교차할 때 까지 반복하면 됩니다.

 

실제로 상황을 보면서 얘기해봅시다. 먼저 l을 pivot보다 큰 값이 나올 때 까지 오른쪽으로 이동하면 12에서 멈춥니다. 그 다음으로 r을 pivot보다 작거나 같은 값이 나올 때 까지 왼쪽으로 이동시킬텐데 애초에 지금 -7이 pivot보다 작으니 이동할 필요 없이 가만히 있으면 됩니다.

 

그럼 지금 pivot보다 큰 12가 왼쪽에 있고 pivot보다 작은 -7은 정작 오른쪽에 있는게 말이 안됩니다. 그렇기 때문에 둘의 자리를 바꿉니다.

 

또 다시 l을 계속 움직이면 8에서 멈추고 r은 3에서 멈춥니다. 그럼 또 이번에도 앞에서 12랑 -7에 대해서 한 것과 마찬가지 이유로 둘의 자리를 바꿉니다.

 

다시 l을 옮기다보면 8에서 멈추고 r은 옮기다가 l보다 왼쪽에 위치한 그 즉시 멈춥니다. 이렇게 r이 l보다 작아진 순간이 오면 pivot과 r을 스왑하면서 알고리즘이 끝납니다.

 

결과를 보면 pivot 왼쪽에는 3, -8, 1, -7이 있고 오른쪽에는 8, 7, 12가 됐으니 pivot이 제자리를 잘 찾아갔습니다. 이 방법이 왜 pivot을 제자리로 잘 보내는지를 이해하려면 모든 순간에 l의 왼쪽에는 pivot보다 작거나 같은 원소들만 있고 r의 오른쪽에는 pivot보다 큰 원소들만 있다는 점에 주목하면 됩니다. 그 사실을 이해하고 다시 과정을 보면 r이 l의 왼쪽에 가는 그 순간에 r과 pivot의 자리를 바꾸면 된다는걸 자연스럽게 받아들일 수 있습니다.

 

그리고 이 방법을 이해한 것과 별개로 코드를 짜는게 썩 쉽지는 않습니다. 무한 루프에 빠지거나 이상한 인덱스를 참고하는 등의 일이 벌어지기 되게 쉽습니다. 한 번 시도해보신다음 제 코드를 같이 보겠습니다.

 

코드는 짤막합니다. 05번째 줄에서 arr[l] <= pivot을 만족하는 동안 l을 계속 1 증가시키다가 while문을 벗어나게 되면 l이 가리키는 곳이 바로 pivot보다 큰 값이 될거고 06번째 줄에서도 상황은 마찬가지입니다. 그리고 이 코드는 상수번의 연산으로 l과 r이 한 칸씩 가까워지기 때문에 O(N)입니다.

 

그리고 이걸 재귀적으로 만들면 퀵 소트가 완성됩니다. base condition은 현재 보는 구간의 길이가 1 이하일 때이고 pivot을 제자리로 보낸 뒤 재귀적으로 자기 자신을 호출하게 하면 됩니다. 링크에 들어가면 주석이 포함된 코드를 볼 수 있습니다. (코드)

 

이렇게 구현을 해낸 것 까지는 좋은데 퀵 소트의 시간복잡도는 얼마일지 고민해봅시다. 일단 퀵 소트의 과정을 풀어헤쳐보면 그림과 같습니다. 맨 처음 pivot은 6이고 6을 기준으로 양쪽이 나뉩니다. 양쪽에서 따로 따로 pivot을 제자리로 보내고, 이렇게 계속 반복합니다.

 

pivot을 제자리로 보내는 시간복잡도는 그 리스트의 크기에 비례하니 각 단계마다 O(N)이 필요하다고 생각할 수 있습니다. 첫 번째 줄이 O(N)인건 자명하고 두 번째 줄을 보면 왼쪽 리스트는 4에 비례하고 오른쪽 리스트는 3에 비례하니 합치면 대략 N에 비례합니다. 이런 식으로 그 단계에서 pivot을 제자리로 보내야 하는 리스트들의 길이의 합은 N이어서 각 단계마다 O(N)이 필요하다고 생각할 수 있습니다. 그러면 pivot이 매번 완벽하게 중앙에 위치해서 리스트를 균등하게 둘로 쪼갠다면 단계의 개수는 머지 소트때와 같이 lg N이 될거고 이 경우에는 퀵 소트의 시간복잡도가 O(NlgN)입니다.

 

물론 늘 pivot이 중앙에 위치하는 이상적인 상황이 생기지는 않겠지만 pivot이 매번 어느 정도로만 잘 자리잡는다면 시간복잡도는 여전히 O(NlgN)입니다. 예를 들어 pivot이 매번 리스트를 1대 99의 배율로 쪼개더라도 시간복잡도는 O(NlgN)이란걸 수학적으로 보일 수 있습니다. 또 앞에서 말한 cache hit rate이 높다는 점 덕분에 퀵 소트는 속도가 굉장히 빠릅니다.

 

그런데 퀵 소트에는 아주 치명적인 단점이 있습니다. 1, 2, 3, 4, 5, 6, 7, 8을 퀵 소트로 정렬하면 시간복잡도가 얼마일지 생각해봅시다. 안타깝게도 매번 선택되는 pivot은 중앙에 가는 대신 제일 왼쪽에 위치하게 되고 그로 인해 단계는 lg N개가 아닌 N개가 됩니다. 그리고 시간복잡도를 계산하면 O(N²)입니다. 이 경우에서 볼 수 있듯이 퀵 소트는 평균적으로 O(NlgN)이지만 최악의 경우 O(N²)입니다. 그리고 단순히 제일 왼쪽의 값을 pivot으로 선택해보면 지금처럼 리스트가 오름차순이거나 내림차순일 때에 바로 O(N²)이 됩니다.

 

STL이 없을 때 정렬을 직접 짜야 한다면 퀵 소트를 절대 쓰지 마라고 맨 처음에 계속 말한 것도 이 이유 때문인데 머지 소트가 퀵 소트보다 느린건 맞지만 어차피 O(NlgN)에 돌아가니 충분히 빠릅니다. 그러면 최악의 경우 O(N²)인 퀵 소트를 절대 쓸 필요가 없습니다. 다시 한 번 말하지만 직접 정렬을 짜야할 때 퀵 소트를 쓰면 안됩니다.

 

그럼 최악의 경우 O(N²)인건 이해했는데 분명 대부분의 라이브러리에서는 퀵 소트를 쓰는 것도 사실입니다. 이런 라이브러리들은 어떤 처리를 했을지 생각해봅시다. 실제 라이브러리를 보면 다양한 처리를 하는데 피벗을 랜덤하게 택할 수도 있고, 피벗 후보를 3개 정해서 그 3개 중에서 중앙값을 피벗으로 두기도 합니다. 그리고 최악의 경우에도 O(NlgN)을 보장하기 위해서 일정 깊이 이상 들어가면 퀵 소트 대신 O(NlgN)이 보장되는 힙 소트로 정렬합니다. 이러한 정렬을 Introspective sort라고 부르고 개인적인 호기심이 있다면 찾아보셔도 좋습니다. 제가 설명한 이정도라도 알아둔다면 퀵 소트에 대해 말을 해야할 때 할 말이 더 풍부해집니다.

 

드디어 머지 소트와 퀵 소트의 끝이 보입니다. 둘 다 재귀적인 구조로 이루어져 있으니 둘을 비교해보고 이번 강의를 마무리하려고 합니다. 먼저 시간복잡도를 보면 머지 소트는 무조건 O(NlgN)이고 퀵 소트는 평균적으로 O(NlgN), 최악의 경우 O(N²)입니다. 단 평균적으로는 퀵 소트가 머지 소트보다 빠릅니다.

 

그리고 추가적으로 필요한 공간은 각각 O(N)과 O(1)입니다. 퀵 소트에서 O(1)이 붙는 이유는 그래도 l, r과 같은 변수를 쓰긴 해서 그렇습니다. 그리고 앞에서 말했지만 퀵 소트는 In-Place Sort입니다. 마지막으로 머지 소트는 우선 순위가 같은 원소들끼리의 원래 순서가 유지되는 Stable Sort이지만 퀵 소트는 아닙니다.

 

이번 강의에서는 머지 소트랑 퀵 소트를 공부했습니다. 다음 시간엔 카운팅 소트와 래딕스 소트, STL sort, 정렬 응용문제를 다룰 예정입니다. 아직 정렬이 끝나지는 않았지만 오늘 다룬 이 2개가 정렬 알고리즘의 두 대장이기 때문에 다음 시간의 내용은 한시름 놓으셔도 됩니다. 두 정렬 모두 직접 한 번 짜보시면 좋겠습니다. 그러면 다음 시간에 만납시다!