비교 정렬

두 값을 비교하는 것에 기반하는 정렬 알고리즘
(비교정렬에서 넘어옴)

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

  1. 이고 이면 이다. (타동성)
  2. 모두 또는 이다. (완전성 또는 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.