정렬(Sorting)은 데이터 구조 분야에서 가장 핵심적인 주제 중 하나로, 그 종류만 해도 200가지가 넘습니다. 이 글에서는 수많은 정렬 기법 중 대표적인 알고리즘들을 선별해 비교 분석해 보겠습니다. 정렬 알고리즘은 크게 비교 기반(comparison-based) 정렬과 비비교 기반(non-comparison-based) 정렬 두 가지로 나눌 수 있습니다.
비교 기반 정렬 알고리즘
버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등이 대표적인 비교 기반 정렬입니다. 이 기법들은 정렬 과정에서 값들을 서로 비교하고, 여러 단계(phase)에 걸쳐 정렬된 위치에 배치하기 때문에 '비교 기반'으로 분류됩니다.
아래 표는 각 알고리즘의 최선(best), 평균(average), 최악(worst)의 경우 시간 복잡도를 정리한 것입니다.
| 분석 유형 | 버블 정렬 | 선택 정렬 | 삽입 정렬 | 병합 정렬 | 퀵 정렬 | 힙 정렬 |
|---|---|---|---|---|---|---|
| 최선의 경우 | O(n2) | O(n2) | O(n) | O(n log n) | O(n log n) | O(n log n) |
| 평균의 경우 | O(n2) | O(n2) | O(n2) | O(n log n) | O(n log n) | O(n log n) |
| 최악의 경우 | O(n2) | O(n2) | O(n2) | O(n log n) | O(n2) | O(n log n) |
비비교 기반 정렬 알고리즘
일부 정렬 알고리즘은 정렬 과정에서 두 요소를 직접 비교하지 않습니다. 라딕스 정렬(Radix Sort), 카운팅 정렬(Counting Sort), 버킷 정렬(Bucket Sort)이 대표적이며, 이런 이유로 '비비교 기반' 정렬로 분류됩니다. 내부 동작 방식은 비교 기반 정렬과 확연히 다르며, 아래 표를 통해 분석 유형별 차이를 확인할 수 있습니다.
| 분석 유형 | 라딕스 정렬 (k = 최대 자릿수) | 카운팅 정렬 (k = 카운트 배열 크기) | 버킷 정렬 (k = 버킷 개수) |
|---|---|---|---|
| 최선의 경우 | O(nk) | O(n + k) | O(n + k) |
| 평균의 경우 | O(nk) | O(n + k) | O(n + k) |
| 최악의 경우 | O(nk) | O(n + k) | O(n2) |
제자리 정렬(In-place)과 제자리 외 정렬(Out-of-place)
정렬 알고리즘은 추가 메모리 사용 여부에 따라서도 구분할 수 있습니다. 정렬 과정에서 별도의 추가 공간을 필요로 하지 않는 알고리즘을 제자리 정렬(in-place sorting)이라고 부릅니다. 퀵 정렬과 힙 정렬이 대표적인 예입니다. 반면 병합 정렬(Merge Sort)은 정렬 결과를 저장하기 위해 추가 배열이 필요한 제자리 외 정렬(out-of-place sorting) 기법입니다.
온라인 정렬과 오프라인 정렬
알고리즘이 새로운 데이터를 처리하는 방식에 따른 구분도 존재합니다. 정렬이 진행되는 도중에 새로운 요소를 받아들여 처리할 수 있는 알고리즘을 온라인 정렬(online sorting)이라고 합니다. 앞서 소개한 기법 중에서는 삽입 정렬(Insertion Sort)이 온라인 정렬에 해당하며, 나머지 대부분의 알고리즘은 전체 데이터가 준비된 후에 정렬을 시작하는 오프라인 방식으로 동작합니다.