6. 비교 기반 정렬 알고리즘(Comparison-based Sorting)

값을 비교하는 것에 기반한 정렬 알고리즘을 비교정렬이라 한다.

(버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 합병 정렬, 퀵 정렬 등)

비교 정렬의 하한 구하기

$n$개의 원소를 비교정렬로 정렬할 경우, 하한Lower Bound을 유도해보자.

$n$개의 유일한 키로부터 존재할 수 있는 순서쌍은 $n!$개이다.
오름차순 정렬을 한다고 가정하면, 이 가운데 단 하나의 순서쌍만이 올바른 정렬 결과이다.

어떤 방법으로 정렬을 하더라도, $n!$개의 경우가 존재하므로 결정 트리의 높이는 최소 $\log (n!)$이 된다.

그러므로, 어떤 비교정렬 알고리즘도 최소 $\log (n!)$ 시간을 소요한다.

$$\log (n!) \leq \log(\frac{n}{2})^{n/2} = \frac{n}{2} \log(\frac{n}{2})$$ 이므로, 어떤 비교정렬 알고리즘이라도 $O(n\log n)$시간이 소요된다.

정렬의 안정성^Stability

키-원소 항목들을 정렬할 때, 중요한 이슈는 동일키의 처리이다.

$L = [(k_0, e_0), \cdots (k_{n-1}, e_{n-1})]$을 정렬해야할 리스트라 하자.

두 개의 항목 $(k_i, e_i)$와 $(k_j, e_j)$에 대해, $k_i=k_j$이며 $i<j$였을 때, 정렬 후에도 $i<j$라면 그 알고리즘을 안정적^stable이라고 한다.

비교정렬 알고리즘 비교

	시간	주요 전략	비고
선택 정렬	$O(n^2)$	(무순) 우선순위 큐	제자리
삽입 정렬	$O(n^2)$	(순서) 우선순위 큐	제자리
힙 정렬	$O(n\log n)$	(힙으로 구현된) 우선순위 큐	제자리 빠름 (대규모 입력에 적합)
합병 정렬	$O(n \log n)$	분할 정복법	순차 데이터접근 빠름 (초대규모 입력에 적합)
퀵 정렬	$O(n \log n)$의 기대시간 (일반적인 경우 가장 빠름)	분할 정복법	제자리, 무작위 접근 가장 빠름 (대규모 입력에 적합)