비교 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Balance à tabac 1850.JPG|섬네일|right|300px|양팔저울만 사용하여 이름이 붙지 않은 추들을 정렬하는 일에는 비교 정렬 알고리즘이 필요하다]]
'''비교 정렬'''은 [[정렬 알고리즘]]의 일종으로 두 값을 비교하는 것에 기반한다. 비교 정렬이 작동하려면 다음 원리가 필요하다.
# <math>a\le b</math>이고 <math>b\le c</math>이면 <math>a\le c</math>이다. (타동성)
# <math>a</math>와 <math>b</math> 모두 <math>a\le b</math> 또는 <math>b\le a</math>이다. (완전성 또는 3분법)

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

== 예 ==
[[파일:Sorting quicksort anim.gif|섬네일|[[퀵 정렬]]의 모습.]]
다음은 잘 알려진 비교 정렬 알고리즘이다.
* [[퀵 정렬]]
* [[힙 정렬]]
* [[셸 정렬]]
* [[합병 정렬]]
* [[인트로소트]]
* [[삽입 정렬]]
* [[선택 정렬]]
* [[거품 정렬]]
* [[홀짝 정렬]]
* [[칵테일 정렬]]
* [[순환 정렬]]
* [[합병 삽입 정렬]]
* [[부드러운 정렬]]
* [[팀 정렬]]

== 참고 문헌 ==
* [[도널드 커누스]]. ''[[컴퓨터 프로그래밍의 예술]]'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0}}. Section 5.3.1: Minimum-Comparison Sorting, pp.&nbsp;180–197.

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]