합병 정렬(merge sort)

분할 정복 알고리즘

 

커다란 문제를 작은 문제로 분할하여 해결해 나가는 방법론

 

 

합병정렬(merge sort) 알고리즘

 

분할 정복 알고리즘을 적용하여 정렬할 배열을 더이상 나눠질 수 없는 배열로 나누어 배열 단위별로 정렬

시간복잡도: O(n log n)

 

배열을 비교하여 정렬

tmp = [None] #임시배열
def merges(li,left,mid,right):#쪼갠 배열을 비교하여 정렬하는 메서드
    l_idx = left # 왼쪽 배열 인덱스
    r_idx = mid +1 # 오른쪽 배열 인덱스
    c_idx = left # 작은수가 들어가는 배열 현재위치
    t_idx = 0 #남은 원소를 한꺼번에 저장할때 사용할 임시 인덱스
    while l_idx <= mid and r_idx <= right: #왼쪽 인덱스가 중간인덱스보다 작고 오른쪽 인덱스가 맨 오른쪽 보다 작을경우 반복
        if li[l_idx] <= li[r_idx]: #왼쪽 값이 오른쪽 값보다 작거나 같을 경우 
            tmp[c_idx] = li[l_idx] # 임시 배열에 왼쪽 값 추가 
            c_idx = c_idx + 1 #현재 위치 값 추가
            l_idx = l_idx + 1 # 왼쪽 인덱스 추가
        else: # 오른쪽 값이 왼쪽 값보다 큰 작은 경우
            tmp[c_idx] = li[r_idx] # 임시 배열에 오른쪽 값 추가
            c_idx = c_idx + 1 
            r_idx = r_idx + 1
    # 왼쪽 인덱스가 mid 보다 커지거나 오른쪽 인덱스가 맨 오른쪽 보다 커질 경우 종료
    if l_idx > mid: # 왼쪽 인덱스가 mid 보다 커진경우 즉 오른쪽 값이 남은 경우
        for t_idx in range(r_idx,right+1,1): #남은 오른쪽 값들을 임시 배열에 추가
            tmp[c_idx] = li[t_idx] 
            c_idx = c_idx + 1
    else: # 오른쪽 인덱스가 right 보다 커진 경우 즉 왼쪽 값이 남은경우
        for t_idx in range(l_idx,mid+1,1): #남은 왼쪽 인덱스 값들을 임시 배열에 추가
            tmp[c_idx] = li[t_idx]
            c_idx = c_idx + 1
    for i in range(0,len(tmp),1): # tmp(임시 리스트) 에 있는 값들을 본 리스트에 추가
        if tmp[i] == None:
            break
        li[i] = tmp[i]
    print(li)

 

배열 나누기

def merge_sort(li,left,right):#배열을 쪼개는 메서드
    mid = 0
    if left == right: #원소가 1개면 종료
        return 0
    mid = int((left + right) / 2)
    merge_sort(li,left,mid) # left~mid 까지 분할
    merge_sort(li,mid+1,right) # mid+1 ~ right 까지 분할
    merges(li,left,mid,right)​

 

실행

list1 = [1,5,10,8,2,3,6,9,4,7]
tmp = tmp * len(list1)
merge_sort(list1,0,len(list1)-1)
print("실행결과")
print(tmp)

 

실행과정 및 결과

[1, 5, 10, 8, 2, 3, 6, 9, 4, 7]
[1, 5, 10, 8, 2, 3, 6, 9, 4, 7]
[1, 5, 10, 2, 8, 3, 6, 9, 4, 7]
[1, 2, 5, 8, 10, 3, 6, 9, 4, 7]
[1, 2, 5, 8, 10, 3, 6, 9, 4, 7]
[1, 2, 5, 8, 10, 3, 6, 9, 4, 7]
[1, 2, 5, 8, 10, 3, 6, 9, 4, 7]
[1, 2, 5, 8, 10, 3, 4, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
실행결과
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]