비교 정렬

양팔저울만 사용하여 이름이 붙지 않은 추들을 정렬하는 일에는 비교 정렬 알고리즘이 필요하다

비교 정렬은 정렬 알고리즘의 일종으로 두 값을 비교하는 것에 기반한다. 비교 정렬이 작동하려면 다음 원리가 필요하다.

1. $a\leq b$이고 $b\leq c$이면 $a\leq c$이다. (타동성)
2. $a$와 $b$ 모두 $a\leq b$ 또는 $b\leq a$이다. (완전성 또는 3분법)

두 값이 같을 때도 있는데, 이 때 값이 입력된 순서대로 정렬된다면 안정적인 정렬이고, 아니라면 불안정적인 정렬이다.

예

퀵 정렬의 모습.

다음은 잘 알려진 비교 정렬 알고리즘이다.

• 퀵 정렬
• 힙 정렬
• 셸 정렬
• 합병 정렬
• 인트로소트
• 삽입 정렬
• 선택 정렬
• 거품 정렬
• 홀짝 정렬
• 칵테일 정렬
• 순환 정렬
• 합병 삽입 정렬
• 부드러운 정렬
• 팀 정렬

참고 문헌

• 도널드 커누스. 컴퓨터 프로그래밍의 예술, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.1: Minimum-Comparison Sorting, pp. 180–197.