공부 삼아 퀵소트를 구현했는데 대부분의 데이터에서는 잘 빠른데, 어떤 입력에서는 갑자기 엄청 느려지고 심하면 재귀가 깊어져서 스택 오버플로까지 나요. 평균은 O(n log n)이라면서 왜 이런 케이스가 생기는지 모르겠습니다.
피벗은 그냥 맨 앞이나 맨 뒤 원소로 잡고 있어요.
def quicksort(a, lo, hi):
if lo >= hi: return
pivot = a[hi] # 항상 마지막 원소
p = partition(a, lo, hi, pivot)
quicksort(a, lo, p - 1)
quicksort(a, p + 1, hi)
느려지는 입력을 살펴보니까 공교롭게도 이미 정렬돼 있거나 거의 정렬된 배열이더라고요. 제 짐작엔 이런 입력에서 파티션이 한쪽으로 확 쏠려서 한 번에 하나씩밖에 못 줄이는 것 같은데, 그러면 재귀 깊이가 n까지 가고 전체가 O(n제곱)이 되는 게 맞을까요?
이럴 때 실무에서는 피벗을 어떻게 고르는지, 랜덤이나 median of three 같은 방법이 실제로 최악을 피하는 데 도움이 되는지 조언 부탁드립니다.