리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.
pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_arr, greater_arr = [], [], []
for num in arr:
if num < pivot:
lesser_arr.append(num) // 분할정복
elif num > pivot:
greater_arr.append(num) // 분할정복
else:
equal_arr.append(num)
return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
공간복잡도
: 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용됨. 스택의 깊이는 n개의 원소에 대해 log(n)에 비례
O(nlog(n))
시간복잡도
최악의 경우(pivot이 최솟값이나 최댓값 선정) : O(n^2)
평균 : O(nlog(n))
1. 메모리 효율이 안좋음
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
low_arr = merge_sort(arr[:mid])
high_arr = merge_sort(arr[mid:])
merged_arr = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
return merged_arr
2. 최적화
def merge_sort(arr):
def sort(low, high):
if high - low < 2:
return
mid = (low + high) // 2
sort(low, mid)
sort(mid, high)
merge(low, mid, high)
def merge(low, mid, high):
temp = []
l, h = low, mid
while l < mid and h < high:
if arr[l] < arr[h]:
temp.append(arr[l])
l += 1
else:
temp.append(arr[h])
h += 1
while l < mid:
temp.append(arr[l])
l += 1
while h < high:
temp.append(arr[h])
h += 1
for i in range(low, high):
arr[i] = temp[i - low]
return sort(0, len(arr))
공간복잡도
: 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요
O(N)
시간복잡도
O(nlog(n))