[TIL] 병합 정렬 Merge Sort Python

병합 정렬

일단 반으로 나누고, 나중에 합쳐서 정렬한다 

 

1. 하나의 리스트를 두 개의 균등한 크기로 분할하고 

2. 분할된 부분 리스트들을 정렬해서 

3. 정렬된 부분 리스트들을 합친다 

 

출처 https://en.wikipedia.org/wiki/Merge_sort

퀵 정렬과의 차이점

	병합 정렬 Merge Sort	퀵 정렬 Quick Sort
시간 복잡도	최악의 경우에도 O(N* logN) 보장	최악의 경우 O(N^2)
진행 방법	정확히 반절씩 나눈다	피벗 값에 따라서 편향되게 분할할 가능성이 있다
공간 복잡도	메모리 활용 비효율적 (기존의 데이터를 담을 추가적인 배열 공간 필요)

 

Merge Sort 를 Python 으로 구현해보기 

 

1번 방식

mergeSort

def mergeSort(a):
    # a 의 길이가 1 이하이면 끝
    if len(a) <= 1:
        return a
    
    # 반으로 나눠서, 앞 부분은 left 뒷 부분은 right 
    mid = len(a)//2
    left = a[:mid]
    right = a[mid:]

    # 모두 분해될 때까지 재귀 
    L = mergeSort(left)
    R = mergeSort(right)

    # 초기 설정은 모두 빈 값으로 선언
    i = j = 0
    result = []

    # i 와 j 가 길이보다 작을 때 while 
    # L[i] 와 R[j] 을 비교하여 result 에 append 
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
        
        # result 에 Left/ Right 합치기 
    result += L[i:]
    result += R[j:]
    return result

 

Main

if __name__ == "__main__":

    num = int(input())
    num_list = [None] * num
    for i in range(num):
        num_list[i] = int(input())

    # mergeSort 로 정렬하고 Print 하기
    sorted_list = mergeSort(num_list)
    
    for i in sorted_list:
        print(i)

 

전체 코드

def mergeSort(a):
    if len(a) <= 1:
        return a
    
    mid = len(a)//2
    left = a[:mid]
    right = a[mid:]

    L = mergeSort(left)
    R = mergeSort(right)

    i = j = 0
    result = []

    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
        
        result += L[i:]
        result += R[j:]
        return result
        
if __name__ == "__main__":

    num = int(input())
    num_list = [None] * num
    for i in range(num):
        num_list[i] = int(input())

    sorted_list = mergeSort(num_list)
    
    for i in sorted_list:
        print(i)

 

 

2번 방식

# 반으로 나눠서 왼쪽 부분의 시작을 left, 
# 오른쪽 부분의 시작을 mid+1 
# 병합 배열의 시작도 left 로 초기값을 준다
# 그리고 left right 차례로 하나씩 비교하기 

# 분할된 부분들을 정렬하는 함수  
def merge(a, temp_a, left, mid, right):
    i = left
    j = mid+1
    k = left

    while i <= mid and j <= right:
        if a[i] <= a[j]:
            temp_a[k] = a[i]
            i += 1
        else:
            temp_a[k] = a[j]
            j += 1
        k += 1

    while i <= mid:
        temp_a[k] = a[i]
        i += 1
        k += 1

    while j <= right:
        temp_a[k] = a[j]
        j += 1
        k += 1

    for i in range(left, right+1):
        a[i] = temp_a[i]

# 분할된 부분들을 병합하는 함수
def iterative(a):
    n = len(a)
    temp_a = [None] * n

    size = 1
    while size < n:
        # 배열의 처음부터 병합 시작 
        left = 0
        # left 가 배열의 끝에 도달할 때까지
        while left < n-1:
            # 
            mid = min(left + size-1, n-1)
            right = min(left + 2*size-1, n-1)
            merge(a, temp_a, left, mid, right)
            left += 1 * size
        size *= 2

if __name__ == '__main__':
    # num_list = list(map(int, input().split()))
    num_list = [3, 4, 2, 1]
    iterative(num_list)
    print(' '.join(map(str, num_list)))

 

 두 방식이 비슷하다고 생각은 했는데 둘 다 시간 초과떠서 의욕이 사라졌다

 근데 좀 정신 차리고 보니까 두 개 같은 방식인 듯,...^_^,..ㅎ