Merge sort, Quick sort비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (5)

Big O 란?

Big O는 시간 복잡도(time complexity)와 관련된 개념입니다. 본격적으로 Big O를 설명하기 전 기본적인 내용을 소개하겠습니다.

일단 프로그래밍 비용에는 두 가지 종류가 있습니다.

1. 실행 비용(Execution cost)
- 시간 복잡도
- 메모리 복잡도

2. 프로그래밍 비용(Programming cost)
- 개발 시간
- 가독성, 수정성, 유지성 

점근적 분석(Asymptotic Analysis)

시간 복잡도는 어떤 코드가 실행하는 데 소요되는 시간을 말합니다. 하지만 모든 코드마다 실행하는 시간을 직접 측정하기 힘들고, 어떤 경우는 슈퍼 컴퓨터를 보유하지 않는 이상 측정이 불가능합니다. 따라서 우리는 수학적 접근 방식을 통해 이를 근사합니다. 전체 데이터 크기 및 반복 루프 등을 고려하여 시간을 추정한 식을 시간 복잡도라고 합니다. 

다만, 중요한 것은 시간 복잡도의 모든 구성 요소에 자세히 신경 쓸 필요는 없다는 것입니다. 예를 들어, 시간 복잡도가 N(N+1)인 알고리즘과 100000N인 알고리즘이 있다고 합시다. 얼핏 보기에는 100000N이 훨씬 클 것 같지만, N이 커지면 커질수록 N(N+1) 값이 압도적으로 커질 것입니다. N이 100000(두 식이 대략적으로 겹치는 지점)이 넘어가면서부터 둘의 차이는 드러나겠죠.

따라서 우리는 N 차원만 중요하게 생각하면 되지, N 앞에 붙은 상수는 사실상 무시해도 괜찮습니다. 해당 차원의 전체적인 모양(기울기가 일정한 일직선 or 급격히 가팔라지는 곡선)만 알면 충분합니다. 

여전히 시간 복잡도를 구할 때 고려할 것이 몇 개 있습니다. 먼저 항상 worst case를 디폴트로 합니다. 즉 한 번에 찾을 수도 있고, 데이터 전체를 뒤져서 찾을 수도 있는 상황에선 낙관적인 상황은 소용이 없습니다. 언제나 최악의 경우라고 가정하고 시간 복잡도를 구해야 합니다. 

다음, $N^2+N+1$ 처럼 2차원 이상의 경우 가장 높은 차원만 보면 됩니다. $N^2+1000000N+1$도 시간 복잡도는 $N^2$에만 관심이 있지, N 앞에 10만, 100만이 붙어도 관심 없습니다. 이 경우 시간 복잡도를 말해라 한다면 $N^2$라고 대답하면 됩니다. 

이는 점근적 분석에서 "Order of growth(증가 기준)" 라고 표현하며 결국 그래프 모양을 나타내는 것입니다. 전체적인 그래프 모양은 가장 높은 차원에 의해 주로 결정되기 때문에 해당 차원만 표시하고 Big O라고 부릅니다. 

형식적인 정의(Formal Definition)를 살펴보겠습니다. 

특정 함수 T(N)의 전체적인 그래프 모양(order of growth 관련)은 f(N)보다 작거나 같다. 이를 다음과 같이 나타낸다. O는 Big-O 표기법이라고 불린다. 

$T(N) \in O(f(N))$

해당 관계를 좀 더 수학적으로 설명하자면 아래와 같다. k는 양수이며, N은 매우 크다고 가정한다.(N이 1, 2일 경우 T(N)이 클 수 있지만 어차피 이는 고려사항에서 제외한다)

$T(N) \le k \cdot f(N)$

함수 T(N)	Order of Growth(Big-O)
$N^2 + 5N^5$	$O(N^5)$
$2/N + 300$	$O(1)$
$Ne^{3N} + 150N^2$	$Ne^{3N}$

3. Merge Sort: 쪼개고 합치자!

전체 리스트를 두 개의 하위 리스트로 구분합니다. 이후 구분된 2개의 리스트에 대해 각각 정렬 작업을 진행하고 정렬된 2개 리스트를 병합합니다. 

그렇다면 구분된 2개 리스트에 대해서 어떻게 정렬 작업을 진행할까요? 아이러니하게도 merget sort 작업을 다시 진행합니다. 이는 재귀적(recursive) 반복 작업이며 재귀에 대해선 조금 있다 설명하겠습니다. 

먼저 재귀적 분할은 아래 그림과 같습니다. 반으로 쪼개고, 쪼개진 sublist별로 다시 쪼개고, 쪼개서 하나만 남을 때까지 작업을 이어나갑니다. 

이제 다 쪼개진 sublist에 대해서 merge 작업을 할 차례입니다. 쪼갰으니 다시 합쳐야겠죠. 대신 각 인덱스 값마다 비교를 해서 정렬해야 합니다. 

아래처럼 sublist에 인덱스가 2개 이상인 경우, 각 sublist의 첫 번째 인덱스끼리 비교 후 최솟값을 선택하여 합쳐진 리스트의 첫 번째 인덱스 값에 채워넣습니다. 이렇게 비교하는 작업을 통해 merge될 리스트를 채워나가면 됩니다. 주의할 점은 아래 예시처럼 sublist1의 모든 인덱스 값이 sublist2보다 작다면 2번만 비교한 후 sublist2 자체를 통으로 붙이면 됩니다. sublist2는 이미 정렬되어 있으니 다시 비교할 필요가 없으니까요. 

Recursion이란? 

재귀란 똑같은 구조를 가진 하위 문제를 포함한 문제를 푸는 것을 말합니다. 위에서 봤듯이, "merge sort는 어떻게 풀어?" 라고 물어본다면 "merge sort를 계속 반복하면 돼" 라고 대답할 수밖에 없습니다. "쪼개고 순서대로 붙이기" 라는 동일한 방법을 가지고 하위 리스트에서 전체 리스트까지 반복 작업하는 것이죠. 

재귀 코드 관련해서 가장 전형적 문제는 팩토리얼 코드를 작성하는 것인데요. 아래를 보시면 facto() 함수 안에 또 facto() 함수를 리턴하는 것을 볼 수 있습니다.

def facto(n: int) -> int:
    if n == 0: # <- 조건문(재귀 반복을 끝내는 조건으로 언젠가 n=0이 될 것이라 확신)
        return 1 # <- 기본 답안
    else:
        return n * facto(n-1) # <- 재귀 반복문 지속 조건 

아래는 또 다른 유명한 문제 피보나치 코드입니다. 피보나치는 1, 2, 3, 5, 8, 13, 21 ... 와 같이 이전 숫자 2개를 더해 현재 값을 구하는 것입니다. 

def fibonacci(n: int) -> int:
    # (1) conditional statement
    if n == 1 or n == 2:
        return n # base case
    else: 
        return fibonacci(n - 2) + fibonacci(n - 1) # (3) recursive case

Merge sort의 시간 복잡도는 반으로 쪼개기 때문에 로그와 관련 있습니다. 어느 단계에서나 리스트 사이즈만큼 시간이 소요되는데, 위의 예시에서 리스트 사이즈는 8개입니다. 위를 거꾸로 자라는 나무 그림이라 생각하고 1층을 전체 리스트라고 생각합시다. 3층에 위치한 인덱스가 2개인 sublist가 4개, 2층에 위치한 인덱스가 4개인 sublist가 2개로 각각 1, 2, 3층 모두 합치면 24만큼 시간이 필요합니다. 

$O(Nlog_{2}^{N})$ 

다만 메모리 복잡도 측면에선 Merge 할때마다 항상 리스트 사이즈만큼 추가로 필요로 합니다. 원본 리스트 자체 내에서 뒤지고 볶고 하는 것이 아니라 새로운 메모리를 할당해서 복사본을 만들기 때문입니다. 

$O(N)$

아래는 merge sort를 코드로 구현한 것입니다.

(참고)
mid = fisrt + (last - first) // 2에서 굳이 (last - first)를 한 이유는 integer overflow라는 것을 방지하기 위함입니다. 이는 비트 연산과 관련된 것인데, 8비트 정수는 0~255, 16비트 정수는 0~65535까지 표현 가능합니다. first=10, last=250일 경우 둘을 더하면 260으로 8비트 정수에서는 표현할 방법이 없어 260-255=5(0, 1, 2, 3, 4), 즉 4로 나타내게 됩니다. 이는 파이썬에서 예외지만, 다른 프로그래밍 언어에선 오류가 날 수 있는 것이라 언급합니다. 

def mergeSortHelp(L: list, first: int, last: int) -> None:
    if first == last: # conditional statement: element가 1개
        return # base case
    else: 
        mid = first + (last-first) // 2 # (last-first) -> integer overflow를 막기 위함
        mergeSortHelp(L, first, mid) # recursive call for sublist1
        mergeSortHelp(L, mid + 1, last) # recursive call for sublist2
        merge(L, first, mid, last) # List copy, not allias -> L 사이즈만큼 메모리 추가 할당(왼쪽+오른쪽, 합친 리스트)
        
def merge(L, first, mid, last):
    k = first
    sub1 = L[first:mid + 1]
    sub2 = L[mid + 1:last + 1]
    i = 0
    j = 0
    while i < len(sub1) and j < len(sub2):
        if sub1[i] <= sub2[j]:
            L[k] = sub1[i]
            i += 1
        else:
            L[k] = sub2[j]
            j += 1
        k += 1        
    
    if i < len(sub1):
        L[k:last + 1] = sub1[i:]
    elif j < len(sub2):
        L[k:last + 1] = sub2[j:]

4. Quick Sort: 잘 분할하자! 

 Quick sort는 파티셔닝(Partitioning)이란 개념이 들어갑니다. 파티셔닝은 한국말로 하면 분할로 해석할 수 있으며, 말 그대로 분할할 지점을 찾는 것입니다. 먼저 기준 원소 p(=pivot)를 선택하고, 분할 지점 k를 찾는데 그 기준은 k 왼쪽 부분은 p보다 작거나 같고, p 오른쪽 부분은 p보다 크거나 같도록 하면 됩니다. (왼쪽, 오른쪽 부분이 정렬되어 있어야 할 필요는 없습니다)

L[:k] <= p 
L[k+1:] >= p 

기준 원소를 랜덤으로 정한 후 적절한 과정을 통해 기준 원소를 옮겨야 한다

파티셔닝의 알고리즘은 다음과 같습니다. 먼저 기준 원소를 정하면 왼쪽, 오른쪽 부분(partition)들로 나뉘겠죠.

1) 왼쪽(i), 오른쪽(j) 부분을 동시에 스캔
2) 잘못된 것이 있으면 두 아이템 위치를 바꿈
3) 기준 원소를 알맞은 자리로 옮김

아래 예시를 보면 i=2에서 7보다 큰 10이 있고, j=10에서 7보다 작은 1이 있습니다. 이 2개의 위치를 서로 바꿔줍니다. 이런 작업을 계속 반복하다 보면 왼쪽 부분에는 모두 7보다 작은 값으로, 오른쪽 부분은 모두 7보다 큰 값으로 구성됩니다. 

위 과정을 거쳐 i=6과 j=8의 위치를 바꿨는데, 기준 원소 7보다 오른쪽에 -1이 위치하게 되죠. 직관적으로 이런 모습이 보기 싫지만(?) 알고리즘 상 기준 원소 오른쪽에 반드시 기준 원소보다 큰 숫자가 위치할 필요는 없습니다. 개념상 왼쪽 부분과 오른쪽 부분에 기준 원소보다 작거나 큰 값이 위치하는 것이 중요하지, 우리 눈에 보이는 위치는 중요하지 않습니다. 

이제 i와 j가 같은 인덱스를 가리킵니다. i 입장에선 2가 정상이지만 j 입장에선 기준 원소 7보다 작기 때문에 비정상임을 감지합니다. 따라서 i는 계속 스캔을 하여 i=8이 되고, j=7인 상태가 됩니다. j < i 가 되었고, 이 경우 알고리즘은 스캔을 멈추게 됩니다. L[:i] 까지는 left partition, L[i:] 은 right partition이 되었습니다.

이때 기준 원소를 다시 정할 필요가 있습니다. left partition은 원래 설정했던 기준 원소보다 다 작은 숫자밖에 없고, right partition은 기준 원소보다 큰 숫자밖에 없습니다. 스캔을 멈출 때 기준 원소가 left partition의 숫자보다 왼쪽에 있다면 left partition의 가장 오른쪽 인덱스와 위치를 바꾸면 됩니다. 

반대로 right partition의 숫자가 모두 기준 원소보다 왼쪽에 위치하면 기준 원소는 right partition의 가장 왼쪽 인덱스와 위치를 바꾸거나, left partition의 숫자가 모두 기준 원소보다 왼쪽에 위치하면 그대로 두면 됩니다. 

파티셔닝의 시간 복잡도와 메모리 복잡도는 아래와 같습니다. Merge sort와 달리 리스트 내에서 swapping을 하기 때문에 추가로 메모리를 잡아먹지 않습니다. 리스트 사이즈 크기와 상관없이 i, j, p 인덱스만 저장하고 비교하면 됩니다. 

i: index starting from the left
j: index starting from the right
p: pivot index
Time cost: O(N)
Memory cost: O(1)

파티셔닝이 끝난 후 리스트의 left partition, right partition에서 각각 정렬되고 서로는 영향을 주지 않습니다. 이때 기준 원소 위치는 변하지 않습니다. left partition의 가장 오른쪽 인덱스에 있든, right partition의 가장 왼쪽 인덱스에 있든 어차피 가장 큰 값 혹은 가장 작은 값이 될테니까요. 

Quick sort의 시간 복잡도는 다음과 같습니다. 먼저 best case를 가정하고 구할텐데, 이전 시간에 시간 복잡도는 worst case를 기본으로 한다고 언급했습니다. 하지만 여기선 이해를 돕고자 best case를 가정할 것이며, Quick sort는 대부분 best case와 같은 시간 복잡도라 사실상 괜찮습니다. best case는 기준 원소를 기준으로 left partition, right partition 크기가 같을 때를 말합니다. 

파티셔닝은 기준 원소보다 작냐, 크냐를 모든 원소에 대해 비교하기 때문에 O(N)입니다. Quick sort에선 각 층마다 파티셔닝이 이루어지기 때문에 Merge sort처럼 반반씩 쪼개지면서 단 하나만 남을 때까지 진행되고, 따라서 $O(Nlog_2^N)$의 시간 복잡도를 가집니다. 

메모리 복잡도 역시 best case를 가정하고 구해봅시다. 메모리 복잡도는 스탭에 주의해야 합니다. 아래 주황색 박스는 Quick sort를 진행할 때 메모리가 계속 사용되고 있는 있음을 나타냅니다.

먼저, 전체 리스트에 대한 인덱스 i, j, p를 사용하고,
다음, 왼쪽 리스트에 대한 인덱스 i, j, p를 사용하고,
다음, 왼쪽 리스트에 대한 인덱스 i, j, p를 사용합니다.

왼쪽 리스트에 대한 작업을 진행할 때 오른쪽 리스트는 작업하지 않습니다. 동시 작업이 아니라 순차적 작업이기 때문에 오른쪽 리스트은 왼쪽 리스트이 끝난 뒤에야 시작합니다. 오른쪽 리스트 파란색 박스 4번은 주황색 박스 3번이 끝난 후 진행됩니다. 파란색 박스도 정렬이 완료되면 주황색 박스 2번이 종료되고, 다음은 파란색 5번 박스에 작업을 합니다. 전체 리스트 주황색 박스 1번은 모든 하위 리스트들이 정렬되야 종료됩니다. 

시간 복잡도는 각 층에선 O(1)이 되지만 전체를 보면 $O(log_2^N)$가 됩니다. 주황색 박스가 최대 몇 개까지 있을 수 있는지(여기선 3개)를 보면 됩니다.

Quick sort의 worst case는 left partition과 right partition이 가장 불균형을 이룰 때, 즉 left partition 크기가 1, right partition 크기가 6일 때입니다. 아래 그림과 같은 상황이 발생하면 시간 복잡도는 $O(N^2)$가 됩니다. 하지만 이런 경우는 극히 드물다고 하네요. 

이제 기준 원소를 선택하는 방법을 살펴보겠습니다. 

1) 가장 왼쪽 원소를 선택하자 <- 간단하지만 위험 
2) 랜덤으로 선택하자 <- 간단하고 평균적으로 괜찮음
3) 중간 원소를 선택하자 <- 가장 좋은 방법이겠지만 중간 원소를 찾는 것 자체가 어려움(찾는 알고리즘 시간 복잡도 = O(N)

3번 접근 방법에 대해 median-of-three rule이라는 것이 있습니다. 2번 랜덤 방법보다 조금 나은 성능을 보이고, 중간 원소를 완벽히 찾을 수 없지만 대략 찾을 수 있다고 합니다. 아래 코드를 참고해주세요. 

def pivotSelect(L: list, low: int, high: int) -> int: # 3개 원소만으로 중간값 구하기
    mid = low + (high-low) // 2
    if L[low] > L[mid]:
        L[low], L[mid] = L[mid], L[low]
    if L[low] > L[high]:
        L[low], L[high] = L[high], L[low]
    if L[mid] > L[high]:
        L[mid], L[high] = L[high], L[mid]
    return mid

이렇게 하면 위에서 언급한 worst case가 나올 확률은 거의 없어진다고 볼 수 있겠죠. 

(참고) 안정성(Stability)이란?

아래 몸무게를 기준으로 정렬을 했습니다. 이때 임영웅과 장민호는 70kg로 같은 몸무게를 가졌지만, 임영웅이 장민호보다 위에 위치한 이유는 이름 순서를 바꾸고 싶지 않기 때문이죠. "임"이 "장"보다 한글 순서상 앞에 위치하므로 이를 바꾸지 않고 그대로 유지시킨 것입니다. 이를 안정성이라고 부릅니다. 

하지만 Quick sort에선 이를 보장할 수 없습니다. 기준 원소보다 크냐, 작냐만을 가지고 서로 위치를 막 바꾸기 때문이죠. Selection sort, Insertion sort, Merge sort는 이런 문제가 없지만, 그래도 Quick sort는 3가지 방법보다 빠르다는 장점이 있습니다.