비교 정렬
보이기
비교 정렬은 정렬 알고리즘의 일종으로 두 값을 비교하는 것에 기반한다. 비교 정렬이 작동하려면 다음 원리가 필요하다.
- 이고 이면 이다. (타동성)
- 와 모두 또는 이다. (완전성 또는 3분법)
두 값이 같을 때도 있는데, 이 때 값이 입력된 순서대로 정렬된다면 안정적인 정렬이고, 아니라면 불안정적인 정렬이다.
예
[편집]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Sorting_quicksort_anim.gif/220px-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. 180–197.