파이썬으로 자료구조 구현해보기-병합정렬

def merge(mixedlist, left, mid, right):
    Lidx, Ridx = left, mid+1
    sortlist = []
    while Lidx <= mid and Ridx <= right:
        if mixedlist[Lidx] <= mixedlist[Ridx]:
            sortlist.append(mixedlist[Lidx])
            Lidx += 1
        else:
            sortlist.append(mixedlist[Ridx])
            Ridx += 1
    if(Lidx > mid):
        for i in range(Ridx, right+1):
            sortlist.append(mixedlist[i])
    else:
        for i in range(Lidx, mid+1):
            sortlist.append(mixedlist[i])
    mixedlist[left:right+1] = sortlist

def mergesort(mixedlist, left, right):
    if left < right:
        mid = (left + right) // 2
        mergesort(mixedlist, left, mid)
        mergesort(mixedlist, mid+1, right)
        merge(mixedlist, left, mid, right)

import random
mixedlist = [random.randint(1, 10) for _ in range(10)]
print("정렬 전: ", mixedlist)
mergesort(mixedlist, 0, 9)
print("정렬 후: ", mixedlist)

책 보고 구현해봤는데 C 말고 파이썬으로 구현하니까 훨씬 쉬운 것 같긴 합니다.
근데 병합 정렬은 정렬하면서 순서의 변환이 안 되니까
2차원 배열에 쓰기도 좋아 보여서 변형해 봤습니다.

def merge(mixedlist, left, mid, right, key):
    Lidx, Ridx = left, mid+1
    sortlist = []
    while Lidx <= mid and Ridx <= right:
        if mixedlist[Lidx][key] <= mixedlist[Ridx][key]:
            sortlist.append(mixedlist[Lidx])
            Lidx += 1
        else:
            sortlist.append(mixedlist[Ridx])
            Ridx += 1
    if(Lidx > mid):
        for i in range(Ridx, right+1):
            sortlist.append(mixedlist[i])
    else:
        for i in range(Lidx, mid+1):
            sortlist.append(mixedlist[i])
    mixedlist[left:right+1] = sortlist

def mergesort(mixedlist, left, right, key):
    if left < right:
        mid = (left + right) // 2
        mergesort(mixedlist, left, mid, key)
        mergesort(mixedlist, mid+1, right, key)
        merge(mixedlist, left, mid, right, key)
import random
mixedlist = [[random.randint(1, 10), random.randint(1, 10)] for _ in range(10)]
print("정렬 전: ", mixedlist)
mergesort(mixedlist, 0, 9, 1)
mergesort(mixedlist, 0, 9, 0)
print("정렬 후: ", mixedlist)

뭔가 더 만져볼 수 있을 것 같은데 잘 모르겠습니다.

1 Like