비교 정렬

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
양팔저울만 사용하여 이름이 붙지 않으느 추들을 정렬하는 일에는 비교 정렬 알고리즘이 필요하다

비교 정렬은 하나의 추상적인 비교 동작을 통해 목록 요소들을 읽어내는 정렬 알고리즘의 일종으로, 두 요소 중 어느 것이 최종 정렬 목록에 발생되어야 하는지를 결정한다. 유일한 필수 조건은 조작을 하는 사람이 전체 순서의 속성 중 2가지를 준수해야 한다는 점이다:

  1. ab이고 bc이면 ac이다 (타동성)
  2. ab 모두 ab 또는 ba이다 (완전성 또는 3분법).

abba를 모두 충족하는 것이 가능한데, 이 경우 둘 중 하나가 정렬 순서에서 먼저 온다. 안정적인 정렬에서 이 경우 입력 순서가 정렬 순서를 결정한다.

[편집]

퀵 정렬의 모습.

잘 알려진 비교 정렬 중 일부는 다음을 포함한다:

참고문헌[편집]