반응형
import sys
sys.setrecursionlimit(99999)
input = sys.stdin.readline
# 파티션 구현 (분할)
#pivot보다 작은값은 앞으로 큰값은 뒤로
def partition(array, left, right):
pivotValue = array[right]
pivot = left
for i in range(int(pivot), int(right)):
if array[i] <= pivotValue:
(array[i], array[pivot]) = (array[pivot], array[i])
pivot += 1
(array[pivot], array[right]) = (array[right], array[pivot])
return pivot
# 재귀 구현 (정복)
#하위 배열이 크기가 1이 될때까지 쪼갬
def quickSort(array, left, right):
if left < right:
pivot = partition(array, left, right)
quickSort(array, left, pivot-1)
quickSort(array, pivot+1, right)
return array
N = int(input())
array = []
for i in range(0, int(N)):
array.append(int(input()))
array = quickSort(array, 0, N-1)
for i in array:
print(i)
시간복잡도
1.파티션구현 :
배열 n의 모든 요소를 pivot과 비교 + swap(옵션)한다.
비교연산과 swap연산은 상수시간안에 동작하므로 O(n)이 걸린다.
2. 재귀 구현:
최선의 경우 mergeSort처럼 매번 n/2로 문제 크기를 재귀적으로 줄여나간다면 O(logn)안에 동작한다
하지만 최악의 경우, 트리가 편중돼있으면 재귀함수가 n번 동작하게 된다.
최악의 경우 - O(n^2)
평균,최선 - O(nlogn)
일반적인 케이스에서는 퀵소트가 상수항때문에 유리하다고 하나
알고리즘 문제 풀이에는 확실한 성능의 mergeSort를 써야겠다.
'알고리즘' 카테고리의 다른 글
정렬의 stability (0) | 2021.04.05 |
---|---|
algorithm, part1 | Coursera 과제 하는법 (mac) (0) | 2021.03.16 |
15일차 - 똑똑똑똑똑 (0) | 2021.03.08 |
Devide and Conquer(mergeSort) (0) | 2021.03.08 |
선택 정렬 시간복잡도 (0) | 2021.03.01 |