이 글은 나동빈님의 "이것이 코딩테스트다 with 파이썬"책과 유튜브 강의를
교재로 삼아 공부한 후 나의 이해한 내용을 정리한 글입니다
병합 정렬
핵심 아이디어
정렬이 필요한 요소를 반으로 나누어 정렬 후 합친다
- 나누어진 배열 2개가 새롭게 정렬된 배열 1개를 return한다.
정렬 진행 방식
1 ) 정렬이 필요한 요소를 반으로 나눈다
2 ) 반으로 나눈 두 배열의 요소를 비교하여 작은 값부터 새로운 배열에 넣는다
3 ) 1 ), 2 )의 과정을 반복한다.
4 ) 정렬 완료
기본 코드 구조
def f_merge(arr):
n = len(arr)
if n <= 1:
return
mid = n // 2
left_group = arr[:mid]
right_group = arr[mid:]
f_merge(left_group)
f_merge(right_group)
left = 0
right = 0
merge = 0
while left < len(left_group) and right < len(right_group):
if left_group[left] < right_group[right]:
arr[merge] = left_group[left]
left += 1
merge += 1
else:
arr[merge] = right_group[right]
right += 1
merge += 1
while left < len(left_group):
arr[now] = left_group[left]
left += 1
merge += 1
while right < len(right_group):
arr[now] = right_group[right]
right += 1
merge += 1
return arr코드 설명
병합정렬도 퀵 정렬만큼 빠른 정렬 속도를 자랑하는 알고리즘이다.
개인적으로 퀵 정렬보다 이해하기 쉽고 사용하기 편해서 자주 이용한다.
코드 1
def f_merge(arr):
n = len(arr)
if n <= 1:
return
mid = n // 2
left_group = arr[:mid]
right_group = arr[mid:]
f_merge(left_group)
f_merge(right_group)
병합 정렬의 핵심 아이디어는 배열을 나누어 정렬한 뒤 합치는 것이다.
즉 처음에 매개변수로 가지는 배열을 기준점을 설정한 뒤 왼쪽/오른쪽 그룹으로 나눈다.
코드 1에서, 만약 배열의 원소가 하나라면 나눌 필요가 없으므로 바로 return한다.
mid라는 변수를 선언한 뒤 배열을 2로 나눈 몫을 할당한다.
left_group이라는 변수에 arr배열의 mid 인덱스까지의 배열을,
right_group에는 mid 인덱스부터 끝까지의 배열을 할당 한다.
매개변수로 가지는 배열의 길이가 얼마나 되지는지는 우리가 알 수 없으나,
최대한 반으로 나누어서 정렬해야 한다.
따라서 반으로 나눈 배열을 다시 반으로, 그 배열을 다시 반으로 나누어서 정렬을 보다 쉽게 할 수 있도록 재귀함수를 이용하여 계속해서 반으로 나누어 준다.
- 배열의 원소가 1개라면 최상위의 조건문에서 return되므로 실제로 arr배열은 원소 2개를 가지는 배열일때까지 나누어 진다.
코드 2
left = 0
right = 0
merge = 0
최종적으로 원소가 2개인 배열까지 나누었다면, 이제 나누어진 배열들을 정렬하여 새로운 배열에 넣어야 한다.
그렇게 하기 위해서 left,right, merge라는 변수를 선언/할당 했다.
코드 2에서 left라는 변수는 코드 1에서 설정한 left_group의 최초 인덱스를,
right라는 변수는 right_group의 최초 인덱스,
merge라는 변수를 left_group, right_group의 배열의 요소의 대소를 비교하여 새로운 배열에 넣을때의 인덱스를 의미한다.
새로운 배열에 넣는다고 표현 하였지만 사실 재귀함수 호출 부분에서 arr이 left_group, right_group으로 나누어지기 때문에 새로운 배열에 넣는것이 아니라 재귀함수 호출 부분에서 매개변수로 들어간 arr을 바꿔주는 것이다.
- 예를 들어, arr이 [ 7, 6, 5, 8 ]이라면, left_group은 [ 7, 6 ]이고, right_group은 [ 5, 8 ]이 된다.
- [ 7, 6 ], [ 5, 8 ]을 원래 나누기 전 arr [ 7, 6, 5, 8 ]에 정렬하여 위치를 바꾼 채로 삽입한다는 의미이다.
코드 3
while left < len(left_group) and right < len(right_group):
if left_group[left] < right_group[right]:
arr[merge] = left_group[left]
left += 1
merge += 1
else:
arr[merge] = right_group[right]
right += 1
merge += 1
코드 2에서 left, right, merge변수까지 선언/할당 하였다면 이제 실제로 대소를 비교하여 정렬된 배열을 만드는 부분이 코드 3 부분이다.
설정한 left_group, right_group 둘 중 하나가 모두 삽입 될 때까지 대소를 비교해야 하므로 while문을 설정 한 뒤 탈출 조건을 명시 했다.
left,right 변수는 arr에 삽입 될 때마다 + 1을 해주어 인덱스를 바꾸어 준다(이동시켜준다)
삽입 되는 조건은
left_group [ left ]가 right_group[ right ]보다 작을 때는 left_group [ left ]를,
그 반대의 경우에는 right_group [ right ]를 삽입 한 후 left나 right를 + 1 연산을 해준다.
여기서 주의할 점은 merge 변수에도 + 1을 해주어야 한다는 것이다.
arr에도 원소를 삽입하였으니 당연히 merge를 + 1 해주어 다음 자리에 넣을 수 있게 만들어야 한다.
코드 4
while left < len(left_group):
arr[now] = left_group[left]
left += 1
merge += 1
while right < len(right_group):
arr[now] = right_group[right]
right += 1
merge += 1
return arr코드 3의 while문을 탈출 하는 조건은 위에서 말했듯이 left_group, right_group 둘 중 하나가 모두 arr에 삽입 되었을 때이다.
따라서 코드 4의 코드은 left_group, right_group 중 아직 다 삽입 되지 못하고 남은 배열을 arr에 삽입 시켜 주는 코드이다
여기서는 남은 요소들을 삽입시키기 때문에 따로 대소 비교를 해 줄 필요가 없다.
left, right, merge를 + 1 시켜주는 연산을 유의해주면 된다.
위의 과정들을 모두 진행하고 나면 정상적으로 병합 정렬이 완료된 arr을 return한다.
최종 코드 // 입 출력 결과
arr = [7, 6, 5, 8, 3, 5, 9, 1]
def f_merge(arr):
n = len(arr)
if n <= 1:
return
mid = n // 2
left_group = arr[:mid]
right_group = arr[mid:]
f_merge(left_group)
f_merge(right_group)
left = 0
right = 0
merge = 0
while left < len(left_group) and right < len(right_group):
if left_group[left] < right_group[right]:
arr[merge] = left_group[left]
left += 1
merge += 1
else:
arr[merge] = right_group[right]
right += 1
merge += 1
while left < len(left_group):
arr[now] = left_group[left]
left += 1
merge += 1
while right < len(right_group):
arr[now] = right_group[right]
right += 1
merge += 1
return arr
print(f_merge(arr))
==> [1, 3, 5, 5, 6, 7, 8, 9]