퀵 정렬
퀵 정렬 (Quick Sort)
퀵 정렬(Quick Sort)은 이름처럼 매우 빠른 속도를 자랑하는 효율적인 정렬 알고리즘입니다. 분할 정복(Divide and Conquer) 패러다임을 사용하며, 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 대부분의 프로그래밍 언어에서 표준 정렬 라이브러리의 근간이 될 만큼 널리 사용됩니다.
🚀 퀵 정렬의 동작 원리
퀵 정렬은 '피벗(Pivot)'이라는 기준 값을 사용하여 전체 배열을 나누는 과정을 재귀적으로 반복합니다.
1. 분할 (Divide) : 배열에서 하나의 원소를 '피벗(pivot)'으로 선택합니다. 피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로, 큰 원소들은 모두 오른쪽으로 이동시킵니다. 이 과정을 '분할(Partitioning)'이라고 합니다. 2. 정복 (Conquer) : 분할된 두 개의 부분 배열(피벗의 왼쪽과 오른쪽)에 대해 재귀적으로 퀵 정렬을 수행합니다. 3. 결합 (Combine) : 정복 과정이 끝나면 배열 전체가 정렬되므로, 별도의 결합 과정은 필요 없습니다.
- 피벗 (Pivot) 선택 : 알고리즘의 성능은 피벗을 어떻게 선택하는지에 크게 좌우됩니다. 배열의 첫 번째나 마지막 원소를 선택하는 것이 간단하지만, 최악의 경우를 피하기 위해 중간값(median-of-three)이나 무작위(random) 값을 선택하는 것이 더 좋습니다.
👍 퀵 정렬의 장점과 단점
- 장점 (Advantages)
> * 매우 빠른 평균 속도 : 평균적으로 O(n log n)의 시간 복잡도를 가지며, 실제 실행 속도가 다른 O(n log n) 알고리즘(병합 정렬, 힙 정렬)에 비해 빠른 편입니다. > * 제자리 정렬 (In-place Sort) : 정렬 과정에서 추가적인 메모리 공간을 거의 필요로 하지 않습니다. (재귀 호출을 위한 O(log n)의 스택 공간만 필요)
- 단점 (Disadvantages)
> * 불안정 정렬 (Unstable Sort) : 정렬 과정에서 동일한 값을 가지는 원소들의 상대적인 순서가 바뀔 수 있습니다. > * 최악의 경우 성능 : 이미 정렬된 배열이나 그에 가까운 배열에 대해 가장 왼쪽/오른쪽 원소를 피벗으로 선택하면, 분할이 한쪽으로 치우쳐져 시간 복잡도가 O(n²)까지 나빠집니다.
💡 개발자 핵심 Point
- 퀵 정렬은 이름처럼 평균적으로 매우 빠른 속도와 제자리 정렬이라는 장점 덕분에, 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.
- 병합 정렬(Merge Sort)과의 비교
> * '퀵 정렬': 제자리 정렬, 불안정 정렬, 평균적으로 빠름, 최악의 경우 느림. > * '병합 정렬': 추가 메모리 필요(O(n)), 안정 정렬, 항상 O(n log n) 보장.
- 최악의 경우를 피하기 위해 'Median-of-three' (배열의 첫 값, 중간 값, 마지막 값 중 중간값을 피벗으로 선택)나 'Randomized Pivot' 같은 피벗 선택 전략을 사용하는 것이 좋습니다.
- 대부분의 프로그래밍 언어 표준 라이브러리의 내장 정렬 함수는 퀵 정렬을 기반으로 하되, 특정 상황(e.g., 재귀 깊이가 깊어질 때)에서는 힙 정렬이나 삽입 정렬을 혼용하는 인트로소트(Introsort) 방식을 사용하여 최악의 경우를 방지하고 성능을 최적화합니다.
