Divide and Conquer 3

타키탸키·2021년 3월 11일

Divide and conquer python 알고리즘 알고리즘 패러다임 프로그래밍 프로그래밍 기초

알고리즘

목록 보기

13/18

저번 시간에는 Divide and Conquer 방식으로 합병 정렬을 구현해봤습니다. 이번 시간에는 또 다른 정렬 방법인 퀵 정렬을 Divide and Conquer 방식으로 구현해보겠습니다.

💨 퀵 정렬

퀵 정렬을 배우기 앞서 합병 정렬을 간단히 복습해 봅시다.

Divide 단계에서는 리스트를 둘로 나누고 Conquer 단계에서 각자의 리스트를 정렬하고 Combine 단계에서 정렬된 두 리스트를 합쳤습니다.

리스트를 둘로 나누고 정렬하는 Divide와 Conquer 단계는 수월했던 반면 리스트의 요소를 비교하여 두 리스트를 합치는 Combine 단계는 조금 복잡했습니다.

퀵 정렬(Quick Sort)은 이와 반대입니다. 즉, Conquer 단계와 Combine 단계는 수월한 반면 Divide 단계가 조금 복잡합니다. 이제부터 퀵 정렬의 동작을 정확히 살펴봅시다.

Divide 단계부터 볼까요? 퀵 정렬에서 리스트를 나누는 과정을 파티션(Partition)이라고 부릅니다. 파티션은 두 단계가 있습니다.

첫 번째 단계는 리스트에서 피벗(Pivot) 즉, 기준점을 정해줍니다. 두 번째 단계는 이 피벗을 기준으로 값들을 새로 배치합니다. 피벗보다 더 작은 값은 모두 왼쪽으로, 더 큰 값은 모두 오른쪽으로 배치해주는 것이죠.

이번에는 퀵 정렬을 Divide and Conquer의 세 가지 단계에 적용해보겠습니다.

Divide: 파티션(피벗을 기준으로 수 배치)

Conquer: 피벗 좌우 리스트 각각 정렬

Combine: Conquer 단계에서 전체 리스트 정렬 완료 > 생략

얼핏보면 간단하지만 합병 정렬과 마찬가지로 부분 문제를 정복하는 과정 Conquer 단계가 수월하게 풀리진 않습니다. 재귀적으로 Divide and Conquer를 거쳐야 하기 때문이죠.

💨 퀵 정렬 진행 과정

8개의 요소가 담긴 리스트가 있습니다.

4 8 3 7 2 1 6 5

우선 Divide 단계에서 파티션을 해야합니다. 편하게 마지막에 있는 5를 피벗으로 정합시다. 그럼 5보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 가게 됩니다.

4 3 2 1 5 8 7 6

이제 왼쪽 부분과 오른쪽 부분을 각각 정렬해야 합니다. 이를 위해서는 또 한 번 Divide and Conquer를 거쳐야겠죠?

4 3 2 1
8 7 6

오른쪽부터 봅시다. 이번에도 마지막에 있는 6을 피벗으로 정하겠습니다.

6 8 7

그리고 또 한 번 Divide and Conquer를 진행합니다. 이번엔 7을 기준으로 하죠.

7 8

이때, 또 한 번 Divide and Conquer를 하게 되는데 7보다 작은 수는 없으므로 왼쪽은 비워져 있습니다. 피벗의 오른쪽도 값이 8로 하나기 때문에 이미 정렬되었다고 보면 됩니다.

그럼 [7 8]로 정렬이 완료되고 피벗의 오른쪽 부분은 [6 7 8]이 됩니다.

왼쪽 부분도 마찬가지로 진행하면 됩니다. 반복해서 Divide and Conquer를 진행하다가 피벗을 기준으로 양 옆에 값이 없거나 하나 밖에 남지 않으면 이미 정렬이 된 것으로 간주되어 base case가 됩니다.

이제 차례대로 부분 문제를 정복해 나가면 맨 처음 피봇이었던 5를 기준으로 양 옆이 정렬되고 최종적으로 [1 2 3 4 5 6 7 8]로 리스트 전체가 정렬되면서 퀵 정렬이 종료됩니다.

💨 퀵 정렬 코드

❗ partition 함수 개요

퀵 정렬을 코드로 구현하기에 앞서 partition 함수를 작성해야 합니다.

퀵 정렬에서 가장 어려운 부분에 속하는 Divide 단계에서 파티션이 이루어진다고 했습니다. 파티션은 기준점을 정하는 과정과 이를 기준으로 수를 배치하는 과정으로 이루어져 있습니다. 그런데 이를 코드로 어떻게 구현할 수 있을까요?

함수 partition은 리스트 some_list, 파티션 범위인 start, end로 파라미터를 총 세 개 받습니다. 다시 말해, some_list에 start 인덱스부터 end 인덱스까지 파티션을 진행하는 함수입니다.

파티션이 진행되는 과정에서 리스트를 그룹 네 개로 분류할 수 있습니다.

먼저 가장 마지막 값을 기준점이 되는 피벗으로 잡습니다. 이를 피벗 그룹이라 부르겠습니다.

이제 하나씩 값을 비교해야 하는데 가장 왼쪽에 있는 요소를 'small 그룹'이라 부르겠습니다. 이 곳에는 피벗보다 작은 값들이 속해 있습니다. 다음으로 피벗보다 큰 값이 속한 'big 그룹'과 피벗과 비교를 진행하지 않은 요소들이 속한 'Unknown 그룹'이 있습니다.

코드를 작성할 때 사용할 변수도 미리 생각해보죠. 우선, start와 end는 각각 리스트의 첫 요소와 끝 요소가 됩니다. 이때, end는 피벗과 같은 값이므로 p(피벗)라는 변수에 넣어줄 것입니다.

그리고 big 그룹이 시작되는 인덱스를 b로, Unknown 그룹이 시작되는 인덱스를 i라고 해줍시다.

s     b      i   p = end
15 10 5 12 2 6 9 8

이제 진행 과정을 차근히 살펴보겠습니다.

퀵 정렬이 시작되면 i와 b 둘 다 맨 왼쪽 인덱스를 가리키게 됩니다. 그리고 아직 아무 값도 안 받았기 때문에 모든 요소들이 Unknown 그룹에 속해있습니다.

s/b/i              p = end
 15  10 5 12 2 6 9 8

먼저 i가 가리키고 있는 15와 피벗 8을 비교하면 15는 8보다 크기 때문에 big 그룹에 들어갑니다. 그럼 i만 오른쪽으로 한 단계 갑니다.

s/b  i            p = end
15  10 5 12 2 6 9 8
big

이제 i와 p를 비교하면 10도 8보다 큰 수이기 때문에 big 그룹으로 들어갑니다. 이번에도 i만 오른쪽으로 한 칸 움직입니다.

s/b   i          p = end
15 10 5 12 2 6 9 8
 big

i에 있는 5와 p에 있는 8을 비교하면 5가 더 작기 때문에 small 그룹으로 들어갑니다. 이때, 중요한 것은 small 그룹이 big 그룹보다 앞에 위치해야 되기 때문에 5와 15의 자리를 바꿔야 한다는 점입니다. 그리고 b와 i를 오른쪽으로 한 칸씩 움직여야 합니다.

s      b    i       p = end
5     10 15 12 2 6 9 8
small  big

이런 식으로 파티션이 이루어집니다. 수가 big 그룹에 속하면 i만 오른쪽으로 한 칸 이동하고 수가 small 그룹에 속하면 b가 가리키고 있는 값과 i가 가리키고 있는 값의 자리를 바꿔야 합니다. 그 후, b와 i 모두 오른쪽으로 한 칸씩 이동합니다.

이 과정을 계속해서 반복한 후, i가 마지막 p에 도달하면 b에 위치한 값과 p에 위치한 값을 바꿔주기만 하면 됩니다. 여기까지 오면 피벗을 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽에 정렬됩니다.

s        b          
5 2 6    8   10 15 12 9
small  pivot    big

❗ partition 함수 구현

이제 partition 함수를 코드로 구현할 차례입니다.

partition 함수는 리스트 some_list와 파티션할 범위를 나타내는 두 인덱스 start, end를 파라미터로 받습니다.

partiotion 함수를 통해 some_list의 값들을 피벗과 비교하여 배치하고 피벗의 최종 인덱스를 반환해야 합니다.

이때, 리스트에서 값들의 위치를 바꿔주는 코드가 반복해서 등장하므로 이 동작에 대한 함수를 따로 정의하겠습니다. swap_elements는 두 요소의 위치를 바꿔주는 helper 함수입니다.

def swap_elements(some_list, idx1, idx2):
    some_list[idx1], some_list[idx2] = some_list[idx2], some_list[idx1]

다음으로 partition 함수를 작성합시다. 앞서 개요에서 partition 함수 작성에 필요한 변수들을 살펴봤습니다. 그 중, unknown 인덱스 i와 big 그룹의 인덱스 b, 피벗의 인덱스 p를 선언해줍니다.

start와 end 값은 파라미터를 통해 들어오기 때문에 따로 지정해줄 필요는 없고 변수의 초기값 설정에 활용하면 됩니다. 첫 시작에 b와 i는 start와 같은 인덱스를 가지고, p는 end와 같은 인덱스를 가집니다.

i = start
b = start
p = end

이제 개요의 내용에 따라 차례로 한 줄씩 반복문을 작성하겠습니다. 이 함수의 경우 인덱스의 값을 조건에 따라 증가시켜야 하기 때문에 for문보다는 while문이 더 적합할 것 같네요.

while의 조건 부분에는 반복문의 종료 조건을 적어줘야 합니다. 어떨 때 while문이 종료되어야 할까요? 바로 인덱스 i가 마지막 인덱스인 p에 도달할 때입니다. 즉, i가 p와 같은 값이 되는 것이 while문의 조건 부분이 됩니다.

while i < p:

다음으로 조건문이 필요한데요. 앞서 인덱스 i는 i의 값이 p의 값보다 크든 작든 1씩 증가했고 인덱스 b의 경우 i의 값이 p의 값보다 작은 경우에는 i와 함께 1씩 증가한다는 것을 봤습니다.

따라서, i의 값과 p의 값을 비교해서 i의 값이 p의 값보다 작거나 크면 b의 값을 하나 늘려주고 i 값은 조건과 상관 없이 1씩 늘려줘야 합니다.

또한, i의 값이 p의 값보다 작을 때에는 i의 값과 b의 값의 자리를 서로 바꿔야 한다는 점을 잊지 마세요.

if some_list[i] <= some_list[p]:
    swap_elements(some_list, b, i)
    b += 1
i += 1

이제 while문이 끝나고 i가 p와 같은 값이 될 때의 수행 부분이 필요합니다. 파티션이 끝나면 b의 값과 p의 값의 자리를 바꿔준다 했었죠? 그리고 반환되어야 할 것은 p의 값이기 때문에 p에는 현재 위치인 b가 들어가야 합니다.

swap_elements(some_list, b, p)
p = b

return p

❗ 퀵 정렬 코드 구현

드디어 퀵 정렬 코드를 구현할 차례입니다.

함수 quick_sort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 두 인덱스 start와 end를 받고 리스트를 정렬합니다.

주의할 것은 merge_sort와 달리 quick_sort는 새로운 정렬된 리스트가 아닌 리스트 자체를 정렬한다는 점입니다.

자, 가장 먼저 해야할 것은 base case를 정하는 것이었죠? 리스트의 길이가 점점 줄어드는 합병 정렬과 다르게 퀵 정렬은 리스트의 인덱스만 바뀝니다.

이때, end 인덱스에서 start 인덱스를 빼면 정렬하고자 하는 리스트의 길이가 나오게 되는데요. 이 값이 1보다 작아지면 퀵 정렬은 바로 종료됩니다. 정렬할 리스트의 길이가 1이면 리스트가 이미 정렬된 것으로 보기 때문이죠.

if end - start < 1:
    return

이제 Divide and Conquer의 세 가지 단계에 들어갑시다. 먼저 Divide 단계에서 파티션 과정을 통해 피벗을 기준으로 리스트를 나누고 Conquer 단계에서 피벗 양 옆 부분을 각각 quick_sort 함수로 정렬해야 합니다. 앞서 설명했듯 Combine 단계에서는 따로 할 게 없으니 생략하겠습니다.

우선 피벗의 값을 설정해야 합니다. 피벗의 인덱스는 어떻게 구했죠? 네, 맞습니다. partition 함수가 반환하는 값이 바로 피벗의 인덱스 p입니다. 따라서, p라는 변수에 partition의 결괏값을 저장해줍시다.

p = partition(some_list, start, end)

다음으로 quick_sort 함수를 재귀적으로 호출할 차례입니다. 이때, 재귀적으로 호출하기 위해서는 리스트 범위를 조정해야 합니다. 합병 정렬에서 리스트 슬라이싱을 통해 리스트의 길이를 줄였듯 퀵 정렬에서는 인덱스를 통해 비교 범위를 줄입니다.

quick_sort(some_list, start, p-1)
quick_sort(some_list, p+1, end)

return

피벗 인덱스를 제외한 나머지 범위를 양옆에 설정함으로써 정렬이 두 부분으로 나누어 진행됩니다. 리스트 자체의 정렬을 바꾸는 것이기 때문에 반환값은 None으로 생략합니다.

이제 전체 코드와 예시를 봅시다.

def swap_elements(some_list, idx1, idx2):

    temp = some_list[idx1]
    some_list[idx1] = some_list[idx2]
    some_list[idx2] = temp
    
def partition(some_list, start, end):

    i = start
    b = start
    p = end

    while i < p:
        if some_list[i] <= some_list[p]:
            swap_elements(some_list, b, i)
            b += 1
        i += 1

    swap_elements(some_list, b, p)
    p = b

    return p
    
def quick_sort(some_list, start, end):

    if end - start < 1:
        return
    
    p = partition(some_list, start, end)
    quicksort(some_list, start, p-1)
    quicksort(some_list, p+1, end)
    
    return

list1 = [2, 4, 6, 8, 10, 12, 15, 12]
quick_sort(list1, 0, len(list1) - 1)
print(list1)

list2 = [27, 14, 10, 31, 2, 46, 4, 6, 13]
quick_sort(list2, 0, len(list2) - 1)
print(list2)

[2, 4, 6, 8, 10, 12, 12, 15]
[2, 4, 6, 10, 13, 14, 27, 31, 46]

이번 시간에는 Divide and Conquer를 통해 퀵 정렬을 구현해봤습니다. 개인적으로는 반환값 없이 리스트 자체를 변화시킨다는 점에서 어려움을 느꼈던 것 같습니다. 여러분은 어떠셨나요?

Divide and Conquer 접근법의 핵심은 두 가지입니다. 재귀 함수처럼 base case 구하기와 Divide, Conquer, Combine 세 가지 과정에 적용하기. 이 부분을 잊지 말고 더 다양한 문제에 적용해 보시길 바랍니다.

* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.

타키탸키

There's Only One Thing To Do: Learn All We Can

이전 포스트

Divide and Conquer 2

다음 포스트