(PYTHON)파이썬 알고리즘 - 병합정렬

(PYTHON)파이썬 알고리즘 - 병합정렬

 

정렬된 배열 병합하기

정렬된 배열 2개(a, b)를 하나의 배열로(c) 정렬하며 병합

from typing import Sequence, MutableSequence

def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None:
    """정렬을 마친 배열 a와 b를 병합하여 c에 저장"""
    pa, pb, pc = 0, 0, 0                 # 각 배열의 커서위치를 0으로 설정
    na, nb, nc = len(a), len(b), len(c)  # 각 배열의 원소수를 할당

    while pa < na and pb < nb:  
        if a[pa] <= b[pb]:   # pa와 pb를 비교하여 pa가 같거나 작으면 값을 c[pc]에 저장
            c[pc] = a[pa]
            pa += 1     # pa 커서위치 우측으로 한칸 이동
        else:
            c[pc] = b[pb]   # pb가 작으면 값을 c[pc]에 저장
            pb += 1     # pb 커서위치 우측으로 한칸 이동
        pc += 1     # pc 커서위치 우측으로 한칸 이동

    while pa < na:              # pa가 배열의 끝에 도달하지 못했다면 남은 원소를 c에 복사
        c[pc] = a[pa]
        pa += 1
        pc += 1

    while pb < nb:              # pb가 배열의 끝에 도달하지 못했다면 남은 원소를 c에 복사
        c[pc] = b[pb]
        pb += 1
        pc += 1

if __name__ == '__main__':
    a = [2, 4, 6, 8, 11, 13]    # 정렬된 배열 a[]
    b = [1, 2, 3, 4, 9, 16, 21] # 정렬된 배열 b[]
    c = [None] * (len(a) + len(b))  # 배열 a개수 + b개수 만큼 빈배열을 만들어 c에 할당
    print('정렬을 마친 두 배열의 병합을 수행합니다.')

    merge_sorted_list(a, b, c)  # 배열 a와 b를 병합하여 c에 저장하는 함수 호출

    print('배열 a와 b를 병합하여 배열 c에 저장하였습니다.')
    print(f'배열 a: {a}')
    print(f'배열 b: {b}')
    print(f'배열 c: {c}')

 

 

sorted() 함수, heapq모듈의 merge() 함수로 병합 정렬하기

# a, b배열이 정렬을 마친 상태가 아니어도 적용이 가능하다는 장점
# 속도가 빠르지 않다는 단점이 있음

a = [2, 1, 6, 8, 11, 13]
b = [1, 2, 3, 4, 9, 16, 21]
c = list(sorted(a+b))  # 배열 a와 b를 병합하여 c에 저장

print('배열 a와 b를 병합하여 배열 c에 저장하였습니다.')
print(f'배열 a: {a}')
print(f'배열 b: {b}')
print(f'배열 c: {c}')

# 속도를 빠르게 병합

import heapq

a = [2, 1, 6, 8, 11, 13]
b = [1, 2, 3, 4, 9, 16, 21]
c = list(heapq.merge(a, b))  # 배열 a와 b를 병합하여 c에 저장

print('배열 a와 b를 병합하여 배열 c에 저장하였습니다.')
print(f'배열 a: {a}')
print(f'배열 b: {b}')
print(f'배열 c: {c}')

 

 

병합 정렬 알고리즘

from typing import MutableSequence

def merge_sort(a: MutableSequence) -> None:
    """병합 정렬"""

    def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 재귀적으로 병합 정렬"""
        if left < right:    # left가 right보다 작으면 실행 (최종적으로 1개씩으로 쪼개질때까지 아래가 진행)
            center = (left + right) // 2

            _merge_sort(a, left, center)            # 재귀호출. 배열 앞부분을 병합 정렬 호출 (중간 기준으로 좌측 호출 - 1개가 될 때까지)
            _merge_sort(a, center + 1, right)       # 재귀호출. 배열 뒷부분을 병합 정렬 호출 (중간 기준으로 우측 호출 - 1개가 될 때까지)
            # 재귀호출이 끝나면 아래에서 병합을 하고 다시 돌아감

            p = j = 0
            i = k = left

            while i <= center:  # left부터 center까지 반복
                 buff[p] = a[i]     # 버퍼[p]에 a[i]를 할당. 중간을 기준으로 좌측 배열을 버퍼에 할당
                 p += 1     # p는 최종적으로 center+1이 됨
                 i += 1     # i도 최종적으로 center+!이 됨

            while i <= right and j < p: # i가 right보다 작으면서 j가 p보다 작다면
                 if buff[j] <= a[i]:    # 버퍼[j]값(좌측첫번째배열값)이 a[i]값(우측첫번째값) 보다 같거나 작으면
                     a[k] = buff[j]     # a[left]에 버퍼[j] 값 할당
                     j += 1       # j 우측으로 한칸이동
                 else:      # 버퍼[j]가 a[i]보다 크면 
                     a[k] = a[i]    # a[left]에 a[i]값 할당
                     i += 1     # i 우측으로 한칸이동
                 k += 1     # 정렬된 k(left)도 우측으로 한칸 이동

            while j < p:    # 버퍼[p]에는 버퍼의 최종값이 들어있는데 j가 아직 p까지 못갔다면 버퍼에 값이 남아있는 상황임
                a[k] = buff[j]  # a[k]에 버퍼[j]값을 할당
                k += 1  # k 한칸 이동
                j += 1  # j 한칸 이동

    n = len(a)
    buff = [None] * n           # 작업용 배열을 생성
    _merge_sort(a, 0, n - 1)    # 배열 전체를 병합 정렬
    del buff                    # 작업용 배열을 소멸

if __name__ == '__main__':
    print('병합 정렬을 수행합니다')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    merge_sort(x)       # 배열 x를 병합 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

(PYTHON)파이썬 전체보기

'(PYTHON)파이썬' 카테고리의 글 목록