Programming 기초/Python
[Python 자료구조 #고급정렬2] 병합정렬(merge sort), 퀵 정렬(quick sort), 이중피벗 퀵 정렬(dual pivot quick sort)
코딩상륙작전
2023. 6. 1. 23:31
* 병합 정렬(merge sort)
- 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다.
- 하나의 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략인 분할 정복(divide and conquer) 기법에 바탕을 두고 있다.
- 추가적인 메모리가 필요하다는 단점이 있다.
- 병합단계에서 n번의 비교 연산이 필요하고, 병합 단계가 log_2 n번 필요하므로 비교 연산은 최대 O(n log_2 n)번 필요하다.
- 최악, 평균, 최선의 경우에도 모두 동일한 O(nlog_2 n)시간 복잡도를 갖는다.
▶ 병합 정렬의 주요 처리 과정
- 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 배열의 크기가 1이면 이미 정복된 것이다.
- 병합(Combine, merge): 정렬된 부분 배열들을 하나의 배열에 통합한다.
- 2개의 리스트를 병합(merge)하는 단계에서 실제로 정렬이 이루어진다.
- 병합을 위해서는 2개의 배열(A와 B)이 모두 반드시 정렬되어 있어야 한다.
- 두 배열의 요소들을 처음부터 하나씩 비교하여 두 요소 중에서 더 작은 요소를 새로운 배열 C로 옮기는 과정을 반복.( 새 배열이 필요하다)
# 병합 정렬 알고리즘을 이용해 배열을 오름차순으로 정렬하는 함수
def merge_sort(A, left, right):
if left < right:
mid = (left + right) // 2 # 리스트의 균등 분할
merge_sort(A, left, mid) # 부분 리스트 정렬
merge_sort(A, mid + 1, right) # 부분 리스트 정렬
merge(A, left, mid, right) # 병합
# 병합 함수
# A는 정렬하고자하는 리스트, left는 가장 왼쪽 인덱스, right는 가장 오른쪽 인덱스
def merge(A, left, mid, right):
global sorted # 병합을 위한 추가적인 배열
k = left # 배열 C(정렬된 리스트)의 인덱스
i = left # 배열 A의 인덱스
j = mid + 1 # 배열 B의 인덱스
while i <= mid and j <= right:
if A[i] <= A[j]:
sorted[k] = A[i]
i, k = i + 1, k + 1
else:
sorted[k] = A[j]
j, k = j + 1, k + 1
if i > mid: # 한쪽에 남아 있는 레코드의 일괄 복사
sorted[k : k + right - j + 1] = A[j : right + 1]# 리스트의 슬라이싱 이용
else:
sorted[k : k + mid - i + 1] = A[i : mid + 1] # 리스트의 슬라이싱 이용
A[left : right + 1] = sorted[left : right + 1] # sorted를 원래 배열 A에 복사
sorted = []
arr = [5, 3, 8, 4, 9, 1, 6, 2, 7]
sorted = [0] * len(arr)
merge_sort(arr, 0, len(arr) - 1)
print("MergeSort: ", arr)
---------------------------------------
MergeSort: [1, 2, 3, 4, 5, 6, 7, 8, 9]
* 퀵 정렬(quick sort)
- 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.
- 분할-정복법을 사용한다.
- 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택하고, 피벗보다 작은 요소를 피벗의 왼쪽으로, 피벗보다 큰 요소를 피벗의 오른쪽으로 옮긴다. 이를 순환을 이용하여 리스트를 정렬한다. (여기서는 첫번째 요소를 피벗으로 선택한다.)
- 시간복잡도 최선의 경우 : 리스트 분할이 항상 리스트의 가운데에서 이루어지는 상황이다. O(n log_2 n)이다. 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.
- 시간복잡도 최악의 경우 : 리스트가 계속 불균형하게 나누어지는 경우이다. (이미 정렬된 리스트의 경우) O(n^2)이다.
- 불균형 분할을 완화하기 위해서 리스트 내의 몇 개의 값들 중에서 중간값(median)을 피벗으로 선택하는 방법이 많이 사용된다.
- 퀵 정렬은 다른 O(n log_2 n)의 알고리즘과 비교해도 가장 빠른 것으로 알려져 있다.
# 퀵 정렬 : 배열의 left ~ right 항목들을 오름차순으로 정렬하는 함수
def quick_sort(A, left, right):
if left < right: # 정렬 범위가 2개 이상인 경우
q = partition(A, left, right) # 좌우로 분할
quick_sort(A, left, q - 1) # 왼쪽 부분리스트를 퀵 정렬
quick_sort(A, q + 1, right) # 오른쪽 부분리스트를 퀵 정렬
# 퀵 정렬에서 피벗을 중심으로 두 개의 리스트로 나누는 partition 과정을 구현한 함수
def partition(A, left, right):
low = left + 1 # 왼쪽 부분 리스트의 인덱스(증가방향)
high = right # 오른쪽 부분 리스트의 인덱스(감소방향)
pivot = A[left] # 피벗 설정
while low <= high: # low와 high가 역전되지 않는 한 반복
while low <= right and A[low] <= pivot:
low += 1
while high >= left and A[high] > pivot:
high -= 1
if low < high: # 선택된 두 레코드 교환
A[low], A[high] = A[high], A[low]
A[left], A[high] = A[high], A[left] # 마지막으로 high와 피벗 항목 교환
return high # 피벗의 위치 반환arr = [5, 3, 8, 4, 9, 1, 6, 2, 7]
quick_sort(arr, 0, len(arr) - 1)
print("quick_sort: ", arr)
-----------------------------------
quick_sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]
* 이중피벗 퀵 정렬(dual pivot quick sort)
- 퀵 정렬을 보완하여 2개의 피벗을 사용하는 퀵 정렬이다.
- 이론적인 시간 복잡도는 퀵 정렬과 차이가 없고, 최악의 경우의 시간 복잡도도 O(n^2)이다.
- 일반적인 경우 퀵 정렬보다 성능이 우수하다고 알려져 있어, 자바나 안드로이드의 시스템 정렬로 사용되었다.
# 퀵 정렬
def dp_quick_sort(A, low, high):
if low < high:
lp, rp = partitionDP(A, low, high) # 좌우 피벗의 인덱스를 반환받음
dp_quick_sort(A, low, lp - 1)
dp_quick_sort(A, lp + 1, rp - 1)
dp_quick_sort(A, rp + 1, high)
# 퀵 정렬에서 이중피벗을 중심으로 세 개의 리스트로 나누는 partition 과정을 구현한 함수
# A는 정렬하고자하는 리스트, low는 왼쪽 피벗의 인덱스, high는 오른쪽 피벗의 인덱스
def partitionDP(A, low, high):
if A[low] > A[high]: # 오른쪽 피벗은 왼쪽보다 작지 않아야 함.
A[low], A[high] = A[high], A[low]
j = low + 1 # lp보다 작은 최대 인덱스
g = high - 1 # rp보다 큰 최소 인덱스
k = low + 1 # low+1부터 하나씩 증가
lpVal = A[low] # 왼쪽 피벗 값
rpVal = A[high] # 오른쪽 피벗 값
while k <= g:
if A[k] < lpVal: # A[k]가 왼쪽 피벗보다 작으면
A[k], A[j] = A[j], A[k] # 교환
j += 1
elif A[k] >= rpVal: # 오른쪽 피벗보다 크거나 같으면
while A[g] > rpVal and k < g: # g의 위치를 찾은 후
g -= 1
A[k], A[g] = A[g], A[k] # A[k] <-> A[g]
g -= 1
if A[k] < lpVal: # 변경된 A[k]가 왼쪽 피벗보다 작으면
A[k], A[j] = A[j], A[k] # 다시 교환
j += 1
k += 1
j -= 1
g += 1
A[low], A[j] = A[j], A[low] # 피벗을 제 위치로: j:왼쪽피벗
A[high], A[g] = A[g], A[high] # 피벗을 제 위치로: g:왼쪽피벗
return j, g # 왼쪽과 오른쪽 피벗의 인덱스 반환arr = [7, 3, 8, 5, 9, 1, 6, 2, 4]
dp_quick_sort(arr, 0, len(arr) - 1)
print("dp_quick_sort: ", arr)
---------------------------------------
dp_quick_sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]