[2. 정렬] 분할정복법(Divide and Conquer)

정렬 알고리즘 종류

• Bubble Sort, Selection Sort, Insertion Sort(간단하지만 느림)
• Merge Sort, Quick Sort, Heap Sort(빠름)
• Radix Sort(매우 빠름)

이 중 Merge Sort, Quick Sort, Heap Sort는 분할정복법을 적용하여 풀 수 있다.

• 분할: 풀고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복: 각각의 작은 문제들을 순환적으로 해결
• 합병: 작은 문제의 해들을 합하여 원래 문제에 대한 답을 구함(merging)

 

1. Merge Sort(합병정렬)

1) 정렬과정

- ① 분할: 배열의 길이가 1이 될때 까지 배열을 반복적으로 반으로 나눔($n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4} \cdots \rightarrow 1$)

- ② 정복: 나눠진 각 배열들을 정렬

- ③ 합병: 정렬된 두개의 배열을 합병

 

merge sort 흐름 개념도

 

2) Merge Sort python 코드

A = np.random.randint(20, size=10)
p = 0
r = len(A)-1

def merge_sort(A, p, r):
    '''
    p,q,r: 배열의 index
    분할, 정복, 합병을 거친다
    '''
    if p < r:
        q = (p+r)//2    # 분할
        merge_sort(A, p, q)    # 앞 배열 정복
        merge_sort(A, q+1, r)    # 뒷 배열 정복
        merge(A, p, q, r)
        
        return A
        
    else:
        return None
        
        
def merge(A, p, q, r):
    '''
    정렬되어 있는 두 배열 A[p,... q], A[q+1,,,r]을 병합하여
    정렬된 배열 A[p ,,, r]을 만든다
    '''
    tmp = [0]*len(A)
    i = p; j=q+1; k = p
    
    while i<=q and j<=r:
        if A[i] <= A[j]:
            tmp[k] = A[i]
            i += 1
        else:
            tmp[k] = A[j]
            j += 1
        k += 1
    while i<=q:
        tmp[k] = A[i]
        i+=1; k+=1
    while j<=r:
        tmp[k] = A[j]
        j+=1; k+=1
    
    A[p:r+1] = tmp[p:r+1]

병합 부분에서 배열의 일부만 정렬하게 되므로 배열을 global로 정의하였다.

 

 

2. Quick Sort

1) 정렬과정

⓪배열에서 정렬에 사용될 기준이 되는 값(pivot)을 선택한 후

- ①분할: pivot보다 작은 값들의 배열, pivot보다 큰 값들의 배열로 분할

- ②정복: 각 배열을 정렬한다

- ③합병: Nothing to do

 

quick sort 정렬 흐름

 

2) Quick Sort Python 코드

def quick_sort(A, p, r):
    if p<r:
        q = partition(A, p, r)  # q는 두 배열 사이에서의 pivot의 위치
        quick_sort(A, p, q-1)  # pivot 왼쪽 배열을 순환적으로 정렬
        quick_sort(A, q+1, r)   # pivot 오른쪽 배열을 순환적으로 정렬
        
        return A
        

def partition(A, p, r):
    i = p-1  # pivot보다 작은 배열 중 마지막 위치의 index
    j = p  # 현재 검사중인 값의 index
    pivot_value = A[r]
    for j in range(p, r):
        if A[j] <= pivot_value:
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i+1], A[r] = A[r], A[i+1]
           
    return i+1
    
    
A = np.random.randint(20, size=10)
p = 0
r = len(A)-1

print(A)
>> [ 9  1  5  5 13 10 13 13  9  8]

quick_sort(A, p, r)
>> array([ 1,  5,  5,  8,  9,  9, 10, 13, 13, 13])

본 예제에서는 pivot 값을 맨 마지막 값으로 설정했으나 랜덤으로 선택해도 상관없다. 뭘 선택하든 맨 뒤로 보내서 정렬하면 같은 시간복잡도로 정렬된다.

 

 

[References]

• 권오흠 교수, 알고리즘(강의 링크)