CS학습
Quick Sort: 분할 정복(Divide and Conquer) 방식을 사용하는 효율적인 정렬 알고리즘
퀵 정렬은 피벗(pivot)을 기준으로 배열을 분할하여 재귀적으로 정렬하는 알고리즘이다. 평균적으로 O(n log n)의 시간 복잡도를 가지며, 대부분의 경우 다른 정렬 알고리즘보다 빠른 성능을 보인다. 하지만 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있다.
송민성3분 읽기
1. 개념
퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘의 한 종류이다. 배열을 피벗(pivot)이라는 기준으로 두 개의 부분 배열로 분할하고, 각 부분 배열을 재귀적으로 정렬하는 방식으로 작동한다. 피벗은 배열 내의 어떤 원소로도 선택 가능하지만, 일반적으로 배열의 첫 번째, 마지막 또는 중앙 값을 선택한다.
2. 왜 사용하는가
퀵 정렬은 평균적으로 매우 빠른 성능을 제공하기 때문에 널리 사용된다. 다른 정렬 알고리즘(병합 정렬, 힙 정렬 등)과 비교했을 때, 일반적으로 상수 곱셈적인 성능 우위를 가진다. 또한, 제자리 정렬(in-place sort) 알고리즘으로, 추가적인 메모리 공간을 거의 사용하지 않는다.
3. 동작 원리
- 피벗 선택: 배열에서 피벗을 선택한다.
- 분할(Partitioning): 피벗보다 작은 원소들은 피벗의 왼쪽으로, 큰 원소들은 오른쪽으로 이동시킨다. 이 과정에서 피벗의 최종 위치가 결정된다.
- 재귀적 정렬: 피벗을 기준으로 왼쪽과 오른쪽 부분 배열을 재귀적으로 퀵 정렬한다.
- 종료 조건: 부분 배열의 크기가 1 이하가 되면 정렬이 완료된 것으로 간주한다.
4. 코드 예제
python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 예시
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr) # 출력: [1, 1, 2, 3, 6, 8, 10]5. 시간 복잡도 또는 성능 특성
- 최선의 경우: O(n log n) - 피벗이 항상 중앙값에 가까울 때.
- 평균적인 경우: O(n log n) - 대부분의 경우.
- 최악의 경우: O(n^2) - 피벗이 항상 최소값 또는 최대값일 때. (예: 이미 정렬된 배열)
- 공간 복잡도: O(log n) - 재귀 호출 스택의 깊이. (제자리 정렬이므로 추가적인 메모리 사용량은 적다.)
6. 실무 사용 사례
- 데이터베이스 시스템의 정렬 기능
- 대규모 데이터 세트의 정렬
- 파일 시스템의 파일 정렬
- 컴파일러 및 인터프리터의 심볼 테이블 정렬
7. 주의할 점
- 최악의 경우 성능 저하를 방지하기 위해 피벗을 신중하게 선택해야 한다. 무작위 피벗 선택, 중앙값 피벗 선택 등의 방법을 사용할 수 있다.
- 재귀 호출 스택 오버플로우를 방지하기 위해 재귀 깊이를 제한하거나 반복적인 구현을 고려해야 한다.
- 퀵 정렬은 불안정 정렬(unstable sort)이다. 즉, 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에 변경될 수 있다.
8. 핵심 정리
퀵 정렬은 분할 정복 방식을 사용하여 배열을 효율적으로 정렬하는 알고리즘이다. 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 피벗 선택에 따라 최악의 경우 O(n^2)의 성능을 보일 수 있다. 실무에서는 피벗 선택 전략과 재귀 깊이 제한 등을 고려하여 성능을 최적화해야 한다.