정렬 알고리즘
정렬 알고리즘은 주어진 원소를 키의 순서 관계에 따라 재배치하거나 순서 있는 인덱스를 생성한다 알고리즘의 정렬 기법 전반에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다...
| 분류 | 알고리즘 · 정렬 기법 전반 |
|---|---|
| 해결 문제 | 주어진 원소를 키의 순서 관계에 따라 재배치하거나 순서 있는 인덱스를 생성한다 |
| 핵심 동작 | 비교 정렬은 두 키를 비교해 순서를 결정하고, 계수·기수 정렬은 키 구조와 값의 범위를 이용한다 |
| 시간 복잡도 | O(n log n) 또는 키 구조별 |
| 추가 공간 | 가변; 구현별 상이 |
| 주요 전제 | 원소의 비교 관계 또는 키의 순서와 자료 표현이 정의되어야 한다 |
| 대표 활용 | 정렬된 자료는 이진 탐색·병합·중복 제거 등에 활용된다 |
| 참고 자료 | MIT 강의 노트 |
정렬 알고리즘은 주어진 원소를 키의 순서 관계에 따라 재배치하거나 순서 있는 인덱스를 생성한다 알고리즘의 정렬 기법 전반에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.[1]
동작 원리는 다음과 같다. 비교 정렬은 두 키를 비교해 순서를 결정하고, 계수·기수 정렬은 키 구조와 값의 범위를 이용한다. 안정성, 제자리 정렬 여부와 입력 자료의 초기 순서도 알고리즘 선택에 영향을 준다. 구현에서 각 단계의 선택이 최종 결과의 올바른 순서·위치를 유지하는지 확인해야 한다. 반복 또는 재귀의 경계와 동일한 키를 가진 원소의 처리 역시 실행 결과에 영향을 준다.
시간·메모리 성질은 비교 기반 일반 정렬의 최악 하한 Ω(n log n), 비비교 정렬은 키 범위 조건에서 선형 가능 적용하려면 원소의 비교 관계 또는 키의 순서와 자료 표현이 정의되어야 한다 따라서 계산 복잡도는 원소 수뿐 아니라 입력의 정렬 상태, 키 범위 또는 비교·이동 비용처럼 알고리즘이 가정하는 자료 특성과 함께 분석해야 한다.
정렬된 자료는 이진 탐색·병합·중복 제거 등에 활용된다. 같은 O(n log n)이라도 캐시, 메모리 할당, 적은 데이터에서의 상수 비용이 다르다. 동일한 목적의 다른 알고리즘과 비교할 때에는 안정성, 원소 이동의 양, 캐시 접근 패턴, 전처리 필요성과 최악 입력에서의 시간 비용을 함께 검토한다. 구체적인 계산 모델은 대상 자료구조 및 구현에 따라 달라진다.[2]