파이썬 재귀함수를 이용한 병합정렬 알고리즘

첫번째 파일

mergeAlgorithm

 

# 병합정렬
# 병합정렬은 전체리스트가 8개면 8개를 4개로 쪼개고 4개를 2개로
# 2개를 1개로 쪼개서 그 1개의 조각이된 8개를 각각 비교하며 오름차순, 내림차순에 따라서
# 1개에서 다시 2개, 2개에서 다시 4개, 4개에서 8개로 재결합을 한다.

# 숫자로 이루어진 리스트를 병합정렬 알고리즘을 이용해서 오름차순과
# 내림차순으로 정렬하는 모듈을 만들어보자(정렬하는 과정도 출력)

def mSort(ns, asc=True):

    # 더 이상 쪼갤 것이 없을때
    if len(ns) < 2:
        return ns

    # 반으로 쪼갠 인덱스
    midIdx = len(ns) // 2

    # 전체 리스트의 인덱스의 시작부터 반으로 쪼갠 인덱스까지
    # 하지만 여기서 더 나아가서 다시금 내가 내 자신에게 넣어서 돌려줘야하는
    # 재귀함수이기 때문에 아래와같이 쓰지 않고
    # leftNums = ns[:midIdx]
    # 이렇게 정의된 mSort 함수에 넣어준다.
    # 더불어서 asc도 재귀할때마다 초기화가 되기때문에 변동가능성이 있다.
    # 때문에 asc = asc도 추가해준다.
    leftNums = mSort(ns[:midIdx], asc=asc)

    # 반으로 쪼갠 인덱스에서 맨 끝까지
    rightNums = mSort(ns[midIdx:],asc=asc)

    # 쪼갠 이후 재병합
    mergeNums = []
    leftIdx = 0; rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                # 작은걸 먼저 붙인다.
                mergeNums.append(leftNums[leftIdx])
                # 이부분이 이해가 안가지만 한번 위에 append로 리스트에 넣기 되었으니깐
                # 한번 붙인건 제외시킨다는 의미로 이렇게 한다고 한다.
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]

    print(f'mergeNums: {mergeNums}')
    return mergeNums

 

두번째 파일

ex

 

 

import random as rd
import mergeAlgorithm
rNums = rd.sample(range(1,101),20)
print(f'rNums: {rNums}')
print()

# 오름차순출력 (asc가 생략되었기 때문)
print(f'mergeAlgorithm.mSort(rNums): {mergeAlgorithm.mSort(rNums)}')
print()
# 내림차순출력
print(f'mergeAlgorithm.mSort(rNums, asc=False): '
      f'{mergeAlgorithm.mSort(rNums, asc=False)}')

 

출력 결과

 

rNums: [32, 25, 27, 3, 19, 21, 50, 9, 73, 94, 41, 16, 29, 79, 83, 75, 49, 4, 96, 91]

mergeNums: [25, 32]
mergeNums: [3, 19]
mergeNums: [3, 19, 27]
mergeNums: [3, 19, 25, 27, 32]
mergeNums: [21, 50]
mergeNums: [73, 94]
mergeNums: [9, 73, 94]
mergeNums: [9, 21, 50, 73, 94]
mergeNums: [3, 9, 19, 21, 25, 27, 32, 50, 73, 94]
mergeNums: [16, 41]
mergeNums: [79, 83]
mergeNums: [29, 79, 83]
mergeNums: [16, 29, 41, 79, 83]
mergeNums: [49, 75]
mergeNums: [91, 96]
mergeNums: [4, 91, 96]
mergeNums: [4, 49, 75, 91, 96]
mergeNums: [4, 16, 29, 41, 49, 75, 79, 83, 91, 96]
mergeNums: [3, 4, 9, 16, 19, 21, 25, 27, 29, 32, 41, 49, 50, 73, 75, 79, 83, 91, 94, 96]
mergeAlgorithm.mSort(rNums): [3, 4, 9, 16, 19, 21, 25, 27, 29, 32, 41, 49, 50, 73, 75, 79, 83, 91, 94, 96]

mergeNums: [32, 25]
mergeNums: [19, 3]
mergeNums: [27, 19, 3]
mergeNums: [32, 27, 25, 19, 3]
mergeNums: [50, 21]
mergeNums: [94, 73]
mergeNums: [94, 73, 9]
mergeNums: [94, 73, 50, 21, 9]
mergeNums: [94, 73, 50, 32, 27, 25, 21, 19, 9, 3]
mergeNums: [41, 16]
mergeNums: [83, 79]
mergeNums: [83, 79, 29]
mergeNums: [83, 79, 41, 29, 16]
mergeNums: [75, 49]
mergeNums: [96, 91]
mergeNums: [96, 91, 4]
mergeNums: [96, 91, 75, 49, 4]
mergeNums: [96, 91, 83, 79, 75, 49, 41, 29, 16, 4]
mergeNums: [96, 94, 91, 83, 79, 75, 73, 50, 49, 41, 32, 29, 27, 25, 21, 19, 16, 9, 4, 3]
mergeAlgorithm.mSort(rNums): [96, 94, 91, 83, 79, 75, 73, 50, 49, 41, 32, 29, 27, 25, 21, 19, 16, 9, 4, 3]

Process finished with exit code 0