10 병합 정렬

재귀호출을 이용한 정렬

두 그룹으로 나눠서 키를 정렬하고 두그룹에서 더작은애를 하나씩 뽑아서 정렬

쉽게 설명한 병합 정렬 알고리즘

# 쉽게 설명한 병합 정렬 
# 입력 : 리스트 
# 출력 : 정렬된 새 리스트 

def merge_sort(a) :
    n= len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한개 이하
    if n<=1:
        return a
    # 그룹을 나눠서 각각 병합 정렬을 호출하는 과정 
    mid = n//2
    g1=merge_sort(a[:mid]) # 재귀 호출로 첫번째 그룹 지정  # 0 ~mid 미만
    g2=merge_sort(a[mid:]) # 재귀 호출로 두번째 그룹 지정 

    # 두 그룹을 하나로 병합
    result = [] 
    while g1 and g2 :
        if  g1[0] <g2[0]: # 두 그룹의 맨 앞 자료 값을 비교 작은값 pop
            result.append(g1.pop(0)) 
        else:
            result.append(g2.pop(0))
    
    # 남아 있는 자료들을 결과에 추가 
    while g1:
        result.append(g1.pop(0))
    
    while g2:
        result.append(g2.pop(0))
    
    return result


d=[6,8,3,9,10,1,2,4,7,5]
print(merge_sort(d))

재귀호출 내에서 병합정렬이 실행된다.

1. 함수 안에서 자기 자신을 다시 호출
2. 재귀 호출할때 인자로 주어지는 입력 크기가 작아진다.
3. 특정 종료 조건이 만족되면 재귀호출을 종료

일반적인 병합 정렬 알고리즘

#병합 절렬 
# 입력 리스트 
# 출력 (주어진 a 정렬 )

def merge_sort (arr):
    n= len(arr)
    # 종료 조건 : 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음 
    if n<=1 :
        return 
    # 두 그룹을 나누어 각각 병합 정렬을 호출하는 과정 

    mid = n//2 
    group1 =arr[:mid] 
    group2 =arr[mid:]
    merge_sort(group1)
    merge_sort(group2)

    # 두그룹을 하나로 병합 
    idx_g1= 0
    idx_g2= 0
    idx_arr= 0

    while idx_g1<len(group1) and idx_g2 <len(group2) :
        if group1[idx_g1] <group2 [idx_g2]:
            arr[idx_arr] =group1[idx_g1]
            idx_g1 +=1
            idx_arr +=1
        else :
            arr[idx_arr] =group2[idx_g2]
            idx_g2 +=1
            idx_arr +=1
        
    # 남아있는 자료들을 결과에 추가 

    while idx_g1<len(group1):
        arr[idx_arr] = group1[idx_g1]
        idx_g1+=1
        idx_arr+=1
    while idx_g2 <len(group2) :
        arr[idx_arr] =group2[idx_g2]
        idx_g2+=1
        idx_arr +=1

d=[6,8,3,9,10,1,2,4,7,5]
merge_sort(d)
print(d)

계산 복잡도 O(NlogN)