합병 정렬

합병 정렬

입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

가장 작은 부분 문제로 계속 쪼갠 뒤 가장 작게 쪼개진 부분문제들을 점차 합병하면서 최종적으로 큰 문제를 해결하는 알고리즘

1. 가장 작은 부분이 될 때까지 반으로 계속 분할

2. 가장 작은 부분들 2개씩부터 합병하면서 최종적으로 정렬된 하나가 됨

 

참고) 알기 쉬운 알고리즘

 

 

import random

# 가장 작은 조각이 될 때까지 계속 분할 + 가장 작은 부분이 되면 거기서부터 점차 합병
def merge_sort(A):
    if len(A) > 1:
        mid = len(A) // 2
        left = A[:mid]  # 0부터 mid-1까지
        right = A[mid:] # mid부터 끝까지

        # 가장 작은 조각이 될 때까지 계속 분할(가장 작은 부분이 되면 거기서 부터 점차 합병)
        merge_sort(left)
        merge_sort(right)
        
        # 분할된 부분들을 합병
        merge(A, left, right)


# 분할된 부분들(집합left, 집합right) 합병
# 루프를 돌며 k를 증가시키면서 계속 left와 right를 비교해 작은 값 찾아 넣기
def merge(A, left, right):
    k = 0   # 정렬한 데이터를 담는 배열(A)의 인덱스
    i = 0   # left의 인덱스
    j = 0   # right의 인덱스
    
    while (i < len(left) and j < len(right)):
        if (left[i] < right[j]):    # left 인덱스 값이 작으면 left의 값을 A에 추가, left 인덱스 + 1
            A[k] = left[i]
            i += 1
        else:  # right 인덱스 값이 작으면 right의 값을 A에 추가, right 인덱스 + 1
            A[k] = right[j]
            j += 1
        k += 1    # A[k]에 작은값을 넣었으니 그 다음의 작은값을 넣기 위해 다음 인덱스를 가리킴

    # j가 right를 다 돌고 i가 left를 다 돌지 못했을 때 => left에 남은 값은 모두 다 A에 append
    if i < len(left):
        for i in range(i, len(left)):
            A[k] = left[i]
            k += 1
    
    # i가 left를 다 돌고 j가 right를 다 돌지 못했을 때 => right에 남은 값은 모두 다 A에 append
    else:
        for j in range(j, len(right)):
            A[k] = right[j]
            k += 1
            
            
# 실행
arr = [random.randrange(1, 1000) for i in range(10)]
print(arr)

merge_sort(arr)
print(arr)

 

실행 결과