본문으로 이동

비교 정렬

위키백과, 우리 모두의 백과사전.

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

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

  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.