(Python)병합정렬

728x90

병합 정렬은 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬

배열을 왼쪽 절반, 오른쪽 절반으로 분할하여 최소 단위로 쪼갠 후 정렬을 진행.

작은 단위로 쪼갠 배열을 저장할 공간을 사용하기 때문에 추가적인 메모리가 필요하다.

분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 빠른 정렬이나 합병 정렬로 대표되는 정렬 알고리즘

ko.wikipedia.org

항상 일정한 시간 복잡도O(NlogN)를 가진다.

안정적이며 대부분의 경우에서 좋은 성능을 낸다.

병합정렬 은 퀵정렬과 같이 분할정복 이다.

퀵정렬은 평향된분할이 될 수 있지만 병합정렬 정확히 반으로 나눈다.

코드

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


def merge_sort(a):
    n = len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하
    if n <= 1:
        return a
    # 그룹을 나누어 각각 병합 정렬을 호출하는 과정
    mid = n // 2  # 중간을 기준으로 두 그룹으로 나눔
    left = merge_sort(a[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬
    right = merge_sort(a[mid:]) # 재귀 호출로 두 번째 그룹을 정렬
    # 두 그룹을 하나로 병합
    result = []
    while left and right:  # 두 그룹에 모두 자료가 남아 있는 동안 반복
        if left[0] < right[0]: # 두 그룹의 맨 앞 자료 값을 비교
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # left과 right 중 이미 빈 것은 while을 바로 지나감
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

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

재귀함수가 진짜 중요하다,

d 리스트를 받아와서 일단 1개 단위까지 되도록 짜른후 다시 합병하는 방식이다.

그림으로 순서를 표현하면 이렇다