[알고리즘] 병합 정렬

[병합 정렬]

• 자료 구조를 분할하고 각각의 분할된 자료구조를 정렬한 후, 다시 병합하여 정렬한다.
• 병합 정렬은 정확히 반절씩 나눈다는 점에서 늘 항상 \( O(N*logN) \) 의 시간 복잡도를 가집니다.
• 퀵 정렬의 경우 피벗 값에 따라 편향되었을 때, 최악의 경우 \( O(N^2) \) 를 갖는다는 점에서 병합 정렬은 이보다 나은 장점을 갖는다. 하지만 그렇다고 해서 평균적으로 병합 정렬이 더 빠르다는건 아니다.

---

• 분할 단계

가로의 길이는 \(N\), 높이는 \( log_2N \) 이 됩니다.

처리하는 데이터의 갯수는 한번 쪼갤 때 마다, 2의 지수로 증가하기 때문에 N이 아니라 훨씬 적은 \( log_2N\) 만으로 처리 할 수 있게 된 것 입니다.

 

• 병합 단계
  정렬하며 병합해갑니다.

이미 정렬이 되어있는 것을 새롭게 정렬 시키는 것이기 때문에 \( O(N) \) 밖에 들지 않는다.

 

 

좀 더 자세히 과정을 봐보자.

 

왼쪽 자료구조의 i 인덱스 요소 값과 오른쪽 자료구조의 j 인덱스 요소 값을 비교한다.

여기선 왼쪽 자료구조가 더 작았고, i += 1 이 되게 된다.

 

 

다시 위의 과정을 반족한다. 오른쪽 자료구조의 요소값이 더 작았고 j += 1 된다.

 

이러한 과정을 거쳐 전체 비교가 \( O(N) \) 밖에 안걸리게 된 것이다.

---

def merge_sort(datas):
    if len(datas) == 1:
        return datas                      # 자료구조 길이가 1일때, 자료구조를 반환한다.
        
    mid = len(datas)//2
    
    left = merge_sort(datas[:mid])
    right = merge_sort(datas[mid:])
    
    mergelist = []
    i, j = 0, 0
    
    while True:
        if i == len(left):            # left가 mergelist에 다 들어간 상태면
            mergelist += right[j:]    # right의 나머지 요소들을 mergelist에 합쳐준다.
            break
        elif j == len(right):         # right가 mergelist에 다 들어간 상태면
            mergelist += left[i:]     # left의 나머지 요소들을 mergelist에 합쳐준다.
            break
        elif left[i] < right[j]:      # left의 i번째 요소가 더 작으면
            mergelist.append(left[i]) # left의 i번째 요소를 mergelist에 넣어준다.
            i += 1
        else :                         # right의 j번째 요소가 더 작으면
            mergelist.append(right[j]) # right의 j번째 요소를 merglist에 넣어준다.
            j += 1 
    return mergelist                   # merge list 반환

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

'''
[1, 2, 3, 4, 5, 6, 8, 10]
'''

---

[실습1] 1부터 100까지 난수 10개 생성하고 다음의 요구사항을 만족하는 프로그램 만들어보자.

요구사항 1) 병합 정렬 알고리즘을 이용한 난수 정렬 함수 구현
요구사항 2) 내림차순과 오름차순 선택 옵션 추가

import random
import copy
def merge_sort(datas):
    if len(datas) == 1:
        return datas
    mid = len(datas)//2
    left = merge_sort(datas[:mid])
    right = merge_sort(datas[mid:])
    merge_list = []
    i,j = 0,0
    while True:
        if i == len(left):
            merge_list += right[j:]
            break
        elif j == len(right):
            merge_list += left[i:]
            break
        elif left[i] < right[j]:
            merge_list.append(left[i])
            i += 1
        else : 
            merge_list.append(right[j])
            j += 1
    return merge_list


original = [random.choice(range(1,101)) for _ in range(10)]


copyver = copy.deepcopy(original)
print('오름차순 정렬 :')
print(merge_sort(copyver))

print('내림차순 정렬 :')
copyver2 = copy.deepcopy(original)
copyver2 = [ -i for i in copyver2 ]
print([ -i for i in merge_sort(copyver2)])

print('원본 데이터 : ')
print(original)

'''
오름차순 정렬 :
[4, 18, 28, 41, 47, 58, 71, 74, 89, 100]
내림차순 정렬 :
[100, 89, 74, 71, 58, 47, 41, 28, 18, 4]
원본 데이터 :
[18, 58, 100, 47, 41, 74, 4, 28, 71, 89]
'''

 

문제 의도랑은 좀 다르게 풀었는데

 

역정렬 할 때는 보통 다음과 같이 각 요소에 - 붙여준뒤

이를 정렬하고, 출력할 때는 다시 - 붙여서 양수값으로 만들어준 뒤 출력해주면 된다고 합니다.