모두의 파이썬 unit09 병합정렬

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

내림차순

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

def merge_sort(a):
    n=len(a)
    #종료조건:정렬할 리스트 자료개수가 한개 이하이면 정렬할 필요없음

    if n<=1:
        return a

    #그룹을 나누어 각각 병합정렬을 호출하는 과정
    mid=n//2 #중간을 기준으로 두 그룹으로 나뭄
    g1=merge_sort(a[:mid])
    print (g1) #재귀호출로 첫번째 그룹을 정렬
    g2=merge_sort(a[mid:]) #재귀호출로 두번째 그룹을 정렬
    print(g2)

    # 두그룹을 하나로 병합
    result=[] #두그룹을 합쳐 만들 최종결과

    while g1 and g2: #두그룹에 모두 자료가 남아있는 동안 반복
        if g1[0] > g2[0]:
            result.append(g1.pop(0))
        else:
            #g2값이 더 작으면 그 값을 뺴내어 결과로 추가
            result.append(g2.pop(0))
        #아직 남아있는 자료들을 결과에 추가
        #g1 g2중 이미 빈것은 while을 바로 지나감

    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))

오름차순

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

def merge_sort(a):
    n=len(a)
    #종료조건:정렬할 리스트 자료개수가 한개 이하이면 정렬할 필요없음

    if n<=1:
        return a

    #그룹을 나누어 각각 병합정렬을 호출하는 과정
    mid=n//2 #중간을 기준으로 두 그룹으로 나뭄
    g1=merge_sort(a[:mid])
    print (g1) #재귀호출로 첫번째 그룹을 정렬
    g2=merge_sort(a[mid:]) #재귀호출로 두번째 그룹을 정렬
    print(g2)

    # 두그룹을 하나로 병합
    result=[] #두그룹을 합쳐 만들 최종결과

    while g1 and g2: #두그룹에 모두 자료가 남아있는 동안 반복
        if g1[0] <g2[0]:
            result.append(g1.pop(0))
        else:
            #g2값이 더 작으면 그 값을 뺴내어 결과로 추가
            result.append(g2.pop(0))
        #아직 남아있는 자료들을 결과에 추가
        #g1 g2중 이미 빈것은 while을 바로 지나감

    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))

일반적인 병합정렬

#병합정렬
#입력 리스트a
#출력:없음(입력으로 주어진 a가 정렬됨)

def merge_sort(a):
    n=len(a)
    #종료조건: 정렬할 리스트의 자료 개수가 한개 이하이면 정렬할 필요가 없음
    if n<=1:
        return

    #그룹을 나누어 각각 병합 정렬을 호출하는 과정

    mid=n//2 #중간을 기준으로 두그룹으로 나눔
    g1=a[:mid]
    g2=a[mid:]

    merge_sort(g1)
    merge_sort(g2)

    #두그룹을 하나로 병합
    i1=0
    i2=0
    ia=0
    while i1<len(g1) and i2<len(g2):
        if g1[i1]<g2[i2]:
            a[ia]<a[i2]
            i1 += 1
            ia += 1
            print(a)
           
        else:
            a[ia]=g2[i2]
            i2 += 1
            ia += 1
            print(a)
            
    #아직 남아있는 자료들을 추가
    while i1<len(g1):
        a[ia]=g1[i1]
        i1 +=1
        ia +=1
    
    while i2<len(g2):
        a[ia]=g2[i2]
        i2 += 1
        ia += 1

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