**정렬(Sorting)**은 순서가 없는 데이터 집합을 특정 키(Key) 값의 순서대로 재배열하는 작업입니다.
1. 정렬 알고리즘 성능 비교표
| 알고리즘 | 평균 시간복잡도 | 최악 시간복잡도 | 공간복잡도 | 제자리 정렬(In-Place) | 안정성(Stable) |
|---|---|---|---|---|---|
| 선택 정렬 (Selection) | $O(N^2)$ | $O(N^2)$ | $O(1)$ | O | X |
| 삽입 정렬 (Insertion) | $O(N^2)$ | $O(N^2)$ | $O(1)$ | O | O |
| 버블 정렬 (Bubble) | $O(N^2)$ | $O(N^2)$ | $O(1)$ | O | O |
| 퀵 정렬 (Quick) | $O(N log N)$ | $O(N^2)$ | $O(log N)$ | O | X |
| 병합 정렬 (Merge) | $O(N log N)$ | $O(N log N)$ | $O(N)$ | X | O |
| 기수 정렬 (Radix) | $O(dN)$ | $O(dN)$ | $O(N+k)$ | X | O |
2. 주요 알고리즘 핵심 메커니즘
- 선택 정렬: 전체 데이터 중 최소값을 찾아 맨 앞 요소와 교환하는 과정을 반복.
- 삽입 정렬: 정렬된 앞부분 서브 리스트에 새로운 요소를 적절한 위치에 삽입.
- 퀵 정렬 (Quick Sort): **피봇(Pivot)**을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬하는 분할 정복 방식.
- 병합 정렬 (Merge Sort): 전체 배열을 반으로 나눈 후 각각을 정렬하고 합치는 안정적 정렬 방식.
3. 파이썬 기반 퀵 정렬 예시
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)
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# 출력: [1, 1, 2, 3, 6, 8, 10]
4. 정렬의 안정성 (Stability) 개념
**안정 정렬(Stable Sort)**이란 값이 같은 레코드가 여러 개 있을 때, 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 알고리즘을 말합니다. (예: 병합 정렬, 삽입 정렬)
5. 자주 묻는 질문 (Q&A)
Q. 퀵 정렬의 최악 시간 복잡도는 언제 $O(N^2)$이 되나요? A. 피봇(Pivot)이 최댓값이나 최솟값으로 계속 선택되는 경우(이미 정렬된 배열에서 첫 번째 요소를 피봇으로 잡을 때 등)에 발생합니다. 이를 방지하기 위해 랜덤 피봇이나 미디언 피봇 기법을 사용합니다.