quickSort 파이썬 구현 (백준 2750)

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를 써야겠다.