quick sort는 어떻게 동작하며 최악의 경우는 무엇인가요?

Question

Accepted Answer

**Quick sort**는 **pivot(피벗)**을 고르고, 그보다 작은 원소와 큰 원소로 분할한 뒤, 각 쪽을 재귀적으로 정렬하는 분할 정복 정렬입니다. 평균 **O(n log n)**, 최악의 경우 **O(n²)**입니다. ## 개념 분할은 pivot을 최종 정렬 위치에 놓습니다. 왼쪽은 모두 더 작고 오른쪽은 모두 더 큽니다. 양쪽에 재귀합니다. ## 예시 ```python def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] # pivot 선택 left = [x for x in arr if x < pivot] # 더 작음 mid = [x for x in arr if x == pivot] # 같음 right = [x for x in arr if x > pivot] # 더 큼 return quicksort(left) + mid + quicksort(right) quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8] ``` (실제로는 메모리를 절약하기 위해 제자리 분할을 사용합니다.) ## 복잡도 | 경우 | 시간 | 원인 | |------|------|-------| | 최선/평균 | O(n log n) | 균형 잡힌 분할 | | 최악 | O(n²) | 나쁜 pivot으로 이미 정렬됨 | 제자리 quicksort는 O(log n) 스택 공간을 사용합니다. ## 언제 사용하나 / 함정 캐시 친화성과 낮은 오버헤드 덕분에 보통 **실제로 가장 빠르며** 제자리 정렬입니다. O(n²) 최악의 경우는 **무작위** pivot이나 median-of-three pivot으로 피합니다. 안정 정렬이 **아닙니다**. ## 왜 중요한가 Quicksort는 뛰어난 평균 속도와 낮은 메모리 사용 덕분에 많은 표준 라이브러리의 기본 정렬입니다. pivot 선택이 왜 O(n²) 최악의 경우를 유발하는지 이해하면 핵심 교훈을 얻습니다. 평균과 최악의 경우는 크게 갈릴 수 있다는 것입니다. 바로 그 미묘함 때문에 즐겨 다루어지는 면접 주제입니다.

경우	시간	원인
최선/평균	O(n log n)	균형 잡힌 분할
최악	O(n²)	나쁜 pivot으로 이미 정렬됨