퀵 정렬
퀵 정렬은 피벗을 기준으로 작은 원소와 큰 원소를 분할한 뒤 부분 배열을 재귀적으로 정렬한다 알고리즘의 비교 정렬에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.
| 분류 | 알고리즘 · 비교 정렬 |
|---|---|
| 해결 문제 | 피벗을 기준으로 작은 원소와 큰 원소를 분할한 뒤 부분 배열을 재귀적으로 정렬한다 |
| 핵심 동작 | 분할 과정에서 피벗과 각 원소를 비교하고 분할 경계를 조정한다 |
| 시간 복잡도 | 평균 O(n log n), 최악 O(n²) |
| 추가 공간 | 재귀 O(log n) 평균 |
| 주요 전제 | 전체 순서를 제공하는 비교 함수와 유효한 분할이 필요하다 |
| 대표 활용 | 배열의 제자리 정렬에 널리 쓰이며 일반 구현은 안정 정렬이 아니다 |
| 참고 자료 | MIT 강의 노트 |
퀵 정렬은 피벗을 기준으로 작은 원소와 큰 원소를 분할한 뒤 부분 배열을 재귀적으로 정렬한다 알고리즘의 비교 정렬에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.[1]
동작 원리는 다음과 같다. 분할 과정에서 피벗과 각 원소를 비교하고 분할 경계를 조정한다. 분할이 균형적이면 재귀 깊이가 로그 수준이고, 이미 정렬된 입력에 부적절한 피벗을 쓰면 불균형 분할이 이어진다. 구현에서 각 단계의 선택이 최종 결과의 올바른 순서·위치를 유지하는지 확인해야 한다. 반복 또는 재귀의 경계와 동일한 키를 가진 원소의 처리 역시 실행 결과에 영향을 준다.
시간·메모리 성질은 평균 O(n log n), 최악 O(n²) 적용하려면 전체 순서를 제공하는 비교 함수와 유효한 분할이 필요하다 따라서 계산 복잡도는 원소 수뿐 아니라 입력의 정렬 상태, 키 범위 또는 비교·이동 비용처럼 알고리즘이 가정하는 자료 특성과 함께 분석해야 한다.
배열의 제자리 정렬에 널리 쓰이며 일반 구현은 안정 정렬이 아니다. 인트로 정렬은 최악 상황을 막으려고 힙 정렬로 전환한다. 동일한 목적의 다른 알고리즘과 비교할 때에는 안정성, 원소 이동의 양, 캐시 접근 패턴, 전처리 필요성과 최악 입력에서의 시간 비용을 함께 검토한다. 구체적인 계산 모델은 대상 자료구조 및 구현에 따라 달라진다.[2]