병합 정렬

병합 정렬

: 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식

 

 

* 분할 정복 알고리즘 사용

- 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄

- top-down

 

 

시간 복잡도 >> O(nlogn)

 

 

구현

arr = [69, 10, 30, 2, 16, 8, 31, 22]

# 병합하는 과정
def merge(llst, rlst):
    result = []
    lp = rp = 0
    
    # 오른쪽, 왼쪽 리스트의 원소를 차례대로 비교하면서 작은 순으로 새로운 배열에 담기
    while lp < len(llst) and rp < len(rlst):
        if llst[lp] < rlst[rp]:
            result.append(llst[lp])
            lp += 1
        else:
            result.append(rlst[rp])
            rp += 1

    # extend >> 리스트끼리 연결하기
    result.extend(llst[lp:])
    result.extend(rlst[rp:])

    return result

# lst의 정보를 정렬하여 새로운 리스트를 return
# 분할하는 과정
def merge_s(lst):
    if len(lst) == 1:
        return lst

    mid = len(lst) // 2
    left = merge_s(lst[:mid])
    right = merge_s(lst[mid:])
    return merge(left, right)


print(merge_s(arr))

 

 

 

연습문제  - SWEA_5204_병합정렬

 

코드

import sys
sys.stdin = open('5204_input.txt', 'r')

T = int(input())

# 병합하는 작업
def merge(llst, rlst):
    global cnt

    result = []

    lp, rp = 0, 0
    while lp < len(llst) and rp < len(rlst):
        if llst[lp] > rlst[rp]:
            result.append(rlst[rp])
            rp += 1
        else:
            result.append(llst[lp])
            lp += 1

    tmp = len(result)
    result.extend(llst[lp:])

    # 왼쪽 리스트 원소가 더 클때는 cnt += 1
    if tmp != len(result):
        cnt += 1

    result.extend(rlst[rp:])

    return result


# 반으로 쪼개는 작업
def merge_s(lst):

    if len(lst) == 1:
        return lst

    mid = len(lst) // 2
    left = merge_s(lst[:mid])
    right = merge_s(lst[mid:])

    return merge(left, right)




for test_case in range(1, T+1):
    N = int(input())

    arr = list(map(int, input().split()))
    cnt = 0

    res = merge_s(arr)

    print(f'#{test_case} {res[N//2]} {cnt}')