알고리즘 : 병합정렬(merge Sorting) in Python

분할정복법은 큰 문제를 작은 문제로 나누어 해결한 뒤 나중에 통합하는 방법으로
대표적으로 퀵정렬, 병합정렬이 있다.

머신러닝할떄 앙상블 모델도 이런 방식으로 문제를 풀지 않을까 생각된다.

그 중에서도 병합정렬을 파이썬으로 구현해봤는데 우선, 분할을 해보자
list_a = [100, 34, 189, 56, 150, 140, 9, 123]
이러한 리스트가 있을 때 방법은 다음과 같다.

100, 34, 189, 56 ||||||||||||||||||||||| 150, 140, 9, 132 이렇게 두개로 나눈다음에
100, 34, 189, 56 ||||||||||||||||||||||| 150, 140, 9, 132 맨앞 두개를 비교해서 작은걸
aux라는 보조 리스트에 넣는다 aux = [100],
그 뒤엔 34, 189, 56 ||||||||||||||||||||||| 150, 140, 9, 132 각 분할의 앞 두개를 다시 비교해서 작은걸 aux에 넣는다.
aux = [100, 34]
이런 구조를 반복하면 결국 aux안에는 정렬된 값이 최종적으로 들어가게 된다.

코드는 부끄럽지만

def merge2(list_a, low, mid, high):
    i=low
    j= mid+1
    k=low
    while(k <= high) :
        if(i> mid) :
            aux[k] = list_a[j]
            k += 1
            j += 1
        elif(j > high):
            aux[k] = list_a[i]
            k += 1
            i += 1
        elif(list_a[i] > list_a[j]):
            aux[k] = list_a[j]
            k += 1
            j += 1
        else:
            aux[k] = list_a[i]
            k += 1
            i +=1  
    for i in range(low,high+1):
        list_a[i] = aux[i]

이런 구조이다. 안정적 정렬이지만 보조배열을 써야한다는게 최대 단점인듯하다.

이게 분할이고 병합정렬은 각각을 가장 작은 단위인 두개로 자른 다음에 merge로 정렬하는 알고리즘인데 그 과정에서 recusion을 쓴다. 코드는

def mergeSort(list_a, low, high):
    if(low>=high): 
        return 
    mid = int((low+high)/2)
    mergeSort(list_a,low,mid)
    mergeSort(list_a,mid+1,high)
    merge2(list_a,low,mid,high)

재귀로 2개가 될 때까지 자른다음에 merge함수로 정렬한다.

수도코드를 대충짜서 빠르게 코딩한건데 다음에 코드를 더 개선해봐야겠다.