병합 정렬(merge sort)
병합 정렬은...
배열을 앞부분과 뒷부분의 두 그룹으로 나누어
각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.
정렬을 마친 배열의 병합
정렬을 마친 두 배열의 병합과정을 보자.
각 배열에서 주목하는 원소의 값을 비교하여,
작은 쪽의 원소를 꺼내
새로운 배열에 저장한다.
이 작업을 반복하여,
정렬을 마친 배열을 만든다.
merge() 함수는
원소 수가 na인 배열 a와 nb인 배열 b를 병합하여
배열 c에 저장한다.
배열 a, b, c를 스캔할때
주목하는 원소의 인덱스는 각각 pa, pb, pc이다.
이 인덱스를 저장한 변수를 커서라고 하자.
처음에는 맨 앞 원소에 주목하므로 모두 0으로 초기화한다.
아래는
3개의 반복문을 늘어놓는 단순한 병합 알고리즘이다.
병합하는 데 필요한 시간 복잡도는 O(n)이다.
해보겠습니다
def merge_sorted_list(a :Sequence,
b: Sequece, c: Mutable Sequence) -> None:
pa, pb, pc = 0
na = len(a)
nb = len(b)
i = 1
while i <= na+nb-1 :
if a[pa] >= b[pb]:
c.append(b[pb])
pb += 1
i += 1
elif a[pa] <= b[pb]:
c.append(a[pa])
pa += 1
i += 1
음
세개의 반복문을 나열한다고 했으니 이건 아니겠지
정답 코드
def merge_sorted_list(a :Sequence,
b: Sequece, c: Mutable Sequence) -> None:
pa, pb, pc = 0, 0, 0
na, nb, nc = len(a), len(b), len(c)
while pa < na and pb < nb:
if a[pa] <= b[pb]:
c[pc] = a[pa]
pa += 1
else:
c[pc] = b[pb]
pb += 1
pc += 1
while pa < na:
c[pc] = a [pa]
pa += 1
pc += 1
while pb < nb:
c[pc] = b[pb]
pb += 1
pc += 1
아..!!!
c 배열의 크기 뿐만 아니라,
a와 b 배열도 있는 만큼만 넣어야겠지...
c는 인풋값으로 받는가했더니,
크기가 나름? 있는가보네.
그냥 인덱스로 넣어버렸어.
넣을 때마다 포인터도 이동해주고...
다 넣은 다음에
a나 b만 남아있다면
그것들을 그냥 바로 넣어주는 것까지 고려했어...
하....
...
하....
잘했다..좋겠다...
? sorted() 함수로 병합 정렬하기
파이썬에서 제공하는 sorted함수로 병합 정렬은 이렇게 할 수 있다.
c = list(sorted(a+b))
이 방법은
a와 b가 정렬을 마친 상태가 아니어도 적용할 수 있다는 장점이 있지만,
속도가 빠르지 않다는 단점도 있다.
빠르게 병합하려면 다음과 같이,
heapq모듈의 merge() 함수를 이용하면 된다.
c = list(heapq.merge(a,b))
병합 정렬 만들기
아니 방금 만든게 병합 정렬? 아님?
정렬을 마친 배열의 병합을 응용하여,
분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
배열을 앞부분과 뒷부분으로 나눈뒤,
나눈 배열을 각각 정렬하고 나서,
병합하여 배열 정렬을 완료한다.
병합 정렬 알고리즘
배열의 원소 수가 2개 이상인 경우
- 배열의 앞부분을 병합 정렬로 정렬합니다.
- 배열의 뒷부분을 병합 정렬로 정렬합니다.
- 배열의 앞부분과 뒷부분을 병합합니다.
너네 재귀 좋아하지
알았어
비재귀적 표현도 좋아하지
알았어
아무튼 구현을 한다고 합니다...
def merge_sorted(c : Mutable Sequence) -> None:
nc = len(c)
left = 0
right = len(c) - 1
pl = left
pr = right
mid = (pl+pr)//2
if nc != 1:
a = merge_sorted(c[:mid])
b = merge_sorted(c[mid:])
pa, pb, pc = 0, 0, 0
na, nb= len(a), len(b)
while pa < na and pb < nb:
if a[pa] <= b[pb]:
c[pc] = a[pa]
pa += 1
else:
c[pc] = b[pb]
pb += 1
pc += 1
while pa < na:
c[pc] = a [pa]
pa += 1
pc += 1
while pb < nb:
c[pc] = b[pb]
pb += 1
pc += 1
뭔가 만족스럽지않군
나보고 연산 많이 했다고 꼽줄거같은 코드야
스택 쓰면 어떻게 되지
하...
아 스택 쓰려면 비재귀화 시켜야한다고?
갑자기 좀 울고 싶어졌어
def merge_sorted(c : Mutable Sequence) -> None:
nc = len(c)
left = 0
right = len(c) - 1
range = Stack(20)
pl = left
pr = right
mid = (pl+pr)//2
if nc != 1:
if range.peek() == 1:
c = c[:mid]
range.push(1)
elif range.peek() == 2:
c = c[mid:]
range.push(2)
pa, pb, pc = 0, 0, 0
na, nb= len(a), len(b)
while pa < na and pb < nb:
if a[pa] <= b[pb]:
c[pc] = a[pa]
pa += 1
else:
c[pc] = b[pb]
pb += 1
pc += 1
while pa < na:
c[pc] = a [pa]
pa += 1
pc += 1
while pb < nb:
c[pc] = b[pb]
pb += 1
pc += 1
if range.peek() == 1 or range.peek() == 2:
k = range.pop()
하..
이게 아니란 건 알겠다
정답 코드
def merge_sort(a:MutableSequence) -> None:
def merge_sort(a:MutableSequence,
left:int, right: int) -> None:
if left < right:
center = (left + right) // 2
_merge_sort(a, left, center)
_merge_sort(a, center+1, right)
p = j = 0
i = k = left
while i <= center:
buff[p] = a[i]
p += 1
i += 1
while i <= right and j < p:
if buff[j] <= a[i]:
a[k] = buff[j]
j +=1
else:
a[k] = a[i]
i +=1
k +=1
while j < p:
a[k] = buff[j]
k += 1
j += 1
n = len(a)
buff = [None]*n
_merge_sort(a,0,n-1)
del buff
이 부분은 앞과 뒤 병합 과정.
_merge_sort(a, left, center)
_merge_sort(a, center+1, right)
...
buff = [None]*n # 작업용 배열 생성
_merge_sort(a,0,n-1) # 배열 전체를 병합 정렬
음.....
그러니까...
작업용 배열 buff 생성
실제로 정렬 작업을 수행하는 함수 호출.
(함수가 내부에 있으니 이거 먼저 제일 실행 됨)
왼, 오 인덱스, 배열 받음.
left와 right가 나누어질 정도의 배열에서만
또 나누기, 병합 정렬을 시킴.
그럼 아무튼 앞부분과 뒷부분이 정렬됨.
그걸 작업용 배열 buff를 사용하여 병합.
...
buff에 배열 a의 앞부분을 붙여놓고,
(배열 a의 중간값까지)
배열 a의 뒷부분 포인터가 끝까지 도달하기 전,
그리고 앞으로 넣을 원소가 여태까지 넣은 원소보다는 적게,
buff와 a를 비교하여 적은 쪽을 넣는다.
buff가 작으면
배열 a에 buff를 넣고 다음으로 넘기고,
배열 a가 작으면
배열 a에 a를 넣고 다음으로 넘기고,
그러고 나면 k값... a의 현재 앞으로 정렬할 배열 원소의 인덱스를 증가시킴.
그다음
뒷부분 배열에서 넣었던 원소가,
앞부분 배열에서 넣었던 원소 수보다 작다면,
buff에 있는걸 마저 넣고
k값과 뒷부분 배열에서 넣었던 원소를 마저 넣음.
...
p : 복사한 원소 수
i : a의 인덱스
j : buff의 인덱스
k : 병합 중인 a의 인덱스
이렇게 정리하니
이해하기 편하군
i의 인덱스는 다 갔는데
아직 복사 못한 값이 있으면
마지막에 buff에서 덧붙이는 거군.
...
왜 이런 일을?
이해는 잘 되지만...
아... 내가 한건
배열이 한 개일때의 병합 정렬을 구현하지않아서...
좋은 방법인데 챗 지피티한테 물어보니
그냥 1일때? 만 돌려주는 거 빼고 내용은 비슷하네.
아래는 챗지피티 협찬.
from typing import MutableSequence
def merge_sorted(c: MutableSequence) -> MutableSequence:
nc = len(c)
if nc <= 1:
return c
mid = nc // 2
a = merge_sorted(c[:mid])
b = merge_sorted(c[mid:])
pa, pb, pc = 0, 0, 0
na, nb = len(a), len(b)
while pa < na and pb < nb:
if a[pa] <= b[pb]:
c[pc] = a[pa]
pa += 1
else:
c[pc] = b[pb]
pb += 1
pc += 1
while pa < na:
c[pc] = a[pa]
pa += 1
pc += 1
while pb < nb:
c[pc] = b[pb]
pb += 1
pc += 1
return c
# Example usage:
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
result = merge_sorted(arr)
print(result)
내가 여기서 배울만한건...
- 변수를 쓸 때는 무엇을 의미하는 변수인지 명확히 하기.
- 한 개의 배열을 병합 정렬할 때는 임의의 배열을 만들어, 앞과 뒤로 나누어 병합 정렬을 할 수 있다!
꼭 배열이 두 개가 아니어도
병합 정렬로 정렬할 수 있다는 건 꽤 인상깊은걸.
배열 병합의 시간 복잡도는 O(n).
데이터 원소수가 n일 때,
병합 정렬의 단계는 log n부터 필요하므로,
전체 시간 복잡도는 O(n log n)이다.
병합 정렬은
서로 떨어져있는 원소를 교환하는 것이 아니므로,
안정적이다.
