파이썬 병합정렬 알고리즘 merge sort #9

파이썬 병합정렬 알고리즘 merge sort #9

안녕하세요.

 

벌써 알고리즘 9번째 시간입니다. 여러분들의 성원에 여기까지 올 수 있었던 것 같습니다. 감사의 말씀 전합니다.

 

 

정렬과 관련해서는 세번째 시간인데요, 이번에는 재귀 호출을 사용해서 정렬 알고리즘 문제를 풀이해보도록 하겠습니다. 재귀 호출은 이번이 처음이 아닌데요.. 이미 앞선 파이썬 알고리즘 시간이 몇 차례 나왔던 내용입니다.

2020/02/05 - [DB엔지니어가 공부하는 python] - [파이썬_알고리즘] 팩토리얼 구하기 #5 feat.factorial, 재귀호출

[파이썬_알고리즘] 팩토리얼 구하기 #5 feat.factorial, 재귀호출

2020/02/11 - [DB엔지니어가 공부하는 python] - [파이썬_알고리즘] 하노이의 탑 옮기기 feat.재귀호출 #6

[파이썬_알고리즘] 하노이의 탑 옮기기 feat.재귀호출 #6

 

팩토리얼을 구하는 것과 하노이의 탑 옮기기 시간에 다뤄봤던 재귀 호출이네요.

 

이 재귀 호출을 이용해서 더욱 빠르게 정렬 알고리즘 문제를 풀이해보도록 하겠습니다.

 

병합 정렬이란, 리스트 안에 있는 변수들을 두 그룹으로 나누어 각 그룹에서 정렬을 먼저 하고 그 뒤에 각 그룹의 가장 작은 변수들끼리 비교하여 더 작은 변수를 다른 새로운 리스트에 차례로 넣는 방법입니다.

 

그림으로 한번 볼까요?

위 그림과 같은 방법으로 정렬을 만들어 내는 것이 바로 병합 정렬 방법입니다.

 

먼저, 병합 정렬을 파이썬 코드로 간단하게 풀이해 보도록 하겠습니다.

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

def merge_sort(a):
    n = len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요 없음
    if n <= 1:
        return a
    # 그룹을 나누어 각각 병합 정렬을 호출하는 과정
    mid = n // 2  # 중간을 기준으로 두 그룹으로 나눔
    g1 = merge_sort(a[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬
    g2 = merge_sort(a[mid:]) # 재귀 호출로 두 번째 그룹을 정렬
    # 두 그룹을 하나로 병합
    result = []       # 두 그룹을 합쳐 만들 최종 결과
    while g1 and g2:  # 두 그룹에 모두 자료가 남아 있는 동안 반복
        if g1[0] < g2[0]: # 두 그룹의 맨 앞 자료 값을 비교
            # g1의 값이 더 작으면 그 값을 빼내어 결과로 추가
            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의 크기가 1 이하, 즉 하나만 남아 있을 때는 정렬할 필요가 없으므로 재귀 호출을 끝내게 됩니다. 

 

mid = n // 2  # 중간을 기준으로 두 그룹으로 나눔
g1 = merge_sort(a[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬
g2 = merge_sort(a[mid:]) # 재귀 호출로 두 번째 그룹을 정렬

파이썬 코드 중간쯤 있는 이 부분은 전체 리스트를 절반으로 나눠 각각 재귀 호출로 병합 정렬하는 부분입니다. mid라는 변수를 n // 2 로 선언하고 이 mid 라는 변수를 통해서 중간값을 찾아 두 그룹으로 나누게 됩니다.

 

아래 설명 코드를 한번 보시면 좀 더 이해하기 쉬울 수 있습니다.

>>> a = [1,2,3,4,5]
>>> mid = len(a) // 2
>>> mid
2
>>> a[:mid]
[1,2]
>>> a[mid:]
[3,4,5]

이런 식으로 하나의 리스트를 두 개의 리스트로 나눌 수 있습니다. 그러고 나서 아래와 같은 로직으로 구현되게 됩니다.

 

1. 숫자 열 개를 두 그룹(g1, g2)으로 나눕니다.

g1: [6,8,3,9,10]

g2: [1,2,4,7,5]

 

2. 두 그룹을 각각 정렬합니다. (재귀 호출)

g1: [3,6,8,9,10]

g2: [1,2,4,5,7]

 

3. 이젠 두 그룹을 합쳐서 하나의 그룹으로 만듭니다. (병합)

각 그룹의 첫 번째 값을 비교하여 작은 값을 빼내어 결과 리스트로 보냅니다.

g1: [3,6,8,9,10]

g2: [2,4,5,7]

결과 : [1]

 

4. 3번 과정을 반복합니다.

g1: [3,6,8,9,10]

g2: [4,5,7]

결과 : [1,2]

.

.

.

g1: [6,8,9,10]

g2: [4,5,7]

결과 : [1,2,3]

 

이런 식으로 요.

 

5. 이 과정을 반복하다 보면 언젠가 한 그룹의 자료가 다 빠져나가게 됩니다.

g1: [8,9,10]

g2: []

결과 : [1,2,3,4,5,6,7]

 

6. 그럼 g2에는 아무것도 남지 않았으므로 더 이상 비교할 필요 없이 g1의 변수들을 결과 리스트로 넣으면 병합 정렬은 끝나게 됩니다.

g1: []

g2: []

결과 : [1,2,3,4,5,6,7,8,9,10]

 

병합 정렬의 알고리즘 가운데, 위의 2번을 보면 재귀 호출을 통해서 각 그룹의 변수들을 정렬한다고 했습니다. 이것은 지난 하노이의 탑 문제를 재귀 호출로 풀어냈던 것과 마찬가지입니다. 병합 정렬 시 두 그룹으로 나누어 정렬을 실행할 때 역시 병합 정렬로 정렬을 하는 것입니다. 이것이 바로 재귀 호출인 것입니다. 함수 안에서 자기 자신을 다시 호출하는 것, 그것이 재귀 호출입니다.

 

이것을 다른 방법으로도 한번 풀이해 볼까요? 물론 이것도 재귀 호출을 이용한 병합 정렬 알고리즘입니다.

# 병합 정렬
# 입력: 리스트 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] = g1[i1]
            i1 += 1
            ia += 1
        else:
            a[ia] = g2[i2]
            i2 += 1
            ia += 1
    # 아직 남아 있는 자료들을 결과에 추가
    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, 1, 2, 4, 7, 5]
merge_sort(d)
print(d)

어떤가요? 위 소스와 비슷한가요? 조금 다른 점이 있다면, return 값이 없고, 리스트 안의 자료 순서를 직접 바꾼다는 차이가 있습니다.

 

병합 정렬 알고리즘을 분석해 보겠습니다.

 

위 알고리즘처럼 커다란 한 덩어리는 둘로 나누고, 또 둘로 나누어서 분할하여 푸는 방법을 분할 정복(divide and conquer)이라고 합니다. 큰 문제를 잘게 나누어 여러 번의 작은 문제로 풀어낸다는 방법입니다. 분할 정복의 특징은 계산 복잡도를 줄여 줄 수 있다는 점입니다. 일반적인 분할 정복을 이용한 병합 정렬의 계산 복잡도는 O(n*logn)으로 표현합니다. 이는 앞서 배웠던 선택 정렬이나 삽입 정렬의 계산 복잡도인 O(n²) 보다 낮습니다. 따라서 정렬해야 할 자료의 개수가 많은수록 병합 정렬이 다른 선택, 삽입 정렬보다 좋은 성능을 보일 수 있는 것입니다.

 

예를 들어볼까요? 우리나라 국민 5천만 명을 정렬한다고 생각해보면, 입력 크기 n=50,000,000 일 때, n² 은 약 2,500조가 됩니다. 하지만 n*logn은 약 13억 정도 됩니다. 참고로 2,500조는 13억의 200만 배 정도 됩니다. 

 

병합 정렬이 얼마나 더 효율적인지 아시겠죠?

 

세 가지 정렬 알고리즘을 정렬한 자료입니다. 참고하시기 바랍니다!

 

 

이것이 정렬 알고리즘의 마지막 시간이네요, 다음엔 탐색을 해보도록 하겠습니다.

 

감사합니다.

 

 

# 파이썬으로 배우는 알고리즘 컨텐츠는 <모두의파이썬X알고리즘, 길벗>을 참고로 작성하는 포스팅 입니다. 물론 협찬은 없습니다.ㅎㅎ

https://book.naver.com/bookdb/book_detail.nhn?bid=14341699

모두의 파이썬 X 알고리즘

 

 

by.sTricky