알고리즘 기본 중의 기본인 병합 정렬을 정리해야겠다.
개인적으로 알고리즘이던 자료구조던 어떤 방법이 있으면 장 단점을 가지고 있다.
이 장 단점을 아는 것도 중요하겠지만 그것보다 더 중요한건 왜 그 장 단점이 만들어졌냐는 것이다.
병합정렬은 아래와 같은 장점을 가지고 있다.
평균적이고 일정한 시간복잡도(nlogn)
메모리에 넣지 못할 만큼 데이터가 대규모일 때 사용할 수 있다.
단점은
배열을 이용한 자료구조일 경우 공간복잡도가 O(n) 이다.
이유
평균적이고 일정한 시간복잡도
병합정렬은 퀵 정렬과 다르게 pivot의 지정 없이 모든 리스트를 절반으로 나눈다. 때문에 pivot에 따른 시간복잡도가 달라지는 일 없이, 일정한 정렬 시간복잡도를 갖는다.
이것은 약간 느리더라도 안정적이고 일정한 정렬 방법이 필요할 때 의미를 갖는다.
메모리에 넣지 못할 만큼 데이터가 방대할 때 사용할 수 있다.
하위 데이터 집합으로 분할해서 별도의 파일에 저장하고, 다시 병합하는 방식을 통해 메모리가 데이터보다 작을 경우에도 사용할 수 있다.
한번에 모든 데이터를 메모리에 올려야 하는 다른 정렬 방식들과 비교해
병합은 각 파일에서 하나의 요소들을 읽어오면서 비교하는 방식을 통해 정렬할 수 있다.
배열을 이용할 경우 공간복잡도가 커진다.
배열의 경우 제자리에서 분할하고 병합하는 것이 안되기 때문에, result 배열을 만들어 정렬되는 요소들을 저장하는 배열을 하나 더 만들어 주어야 한다.
연결리스트로 병합정렬을 구현하는 경우 공간복잡도가 많이 줄어든다. 새로운 배열을 만들 필요가 없이 인덱스만 변경해주면 되기 때문이다.
이 경우 O(logN) 의 공간 복잡도가 필요하다. 이 공간 복잡도는 병합정렬에서 분할을 실행할 경우 재귀함수의 스택공간이 필요한데 이 내용을 저장할 공간이다.
배열의 경우 O(n)의 공간 복잡도인데 연결리스트와 같이 스택공간이 필요하지만 전체 공간복잡도가 O(logN)보다 크기 때문에 dominate 해서 O(n)이 된다.
구현
def merge_sort(list1):
if len(list1) < 2:
return list1
# 배열을 양쪽으로 나눈다
left_list = list1[0:len(list1)//2]
right_list = list1[len(list1)//2: len(list1)]
# return 값이 없을 때 까지 재귀함수로 분할
# 합치면서 정렬을 하는데...
# merge
left_list = merge_sort(left_list) # 왼쪽
right_list= merge_sort(right_list) # 오른쪽
return merge(left_list, right_list)
def merge(list1, list2):
# left~mid 와 mid ~ right while 문 돌면서 비교 해서 sorted에 넣어줌
result= []
while list1 and list2:
if list1[-1] >= list2[-1]:
result.append(list1.pop())
else:
result.append(list2.pop())
result.reverse()
return (list1 or list2) + result
def solution():
unsorted_list = [3,5,2,6,8,1,0,3,5,6,2]
# 미드 값 지정,
return merge_sort(unsorted_list)
print(solution())
merge_sort() 에서 재귀함수를 통해 분할하고, merge()로 병합한다.
병합은 왼쪽리스트 오른쪽 리스트의 마지막 원소를 비교해서 더 큰 원소부터 새로운 리스트 result에 쌓는다. 그리고 이걸 뒤집어서 리턴하고 계속 반복한다.
이렇게 하면 정렬이 된다.
