문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 정렬 (문단 편집) === 비교 정렬과 비비교 정렬 === ## 적당한 번역어가 없어 구글 검색에서 가장 자주 보이는 '비비교 정렬'이라는 용어를 사용했습니다. 더 적합한 번역어가 있다면 수정해주세요. {{{+1 Comparison sort & Non-comparison sort}}} 위에서 설명한 전순서 관계를 활용하면, 임의의 요소 [math(a)]와 [math(b)]에 대해 항상 누가 앞에 오고 누가 뒤에 오는지를 알 수 있다. 이를 활용하는 것이 바로 비교 정렬이다. 반대로 비교 연산을 사용하지 않는 정렬은 비비교 정렬, 일반 정렬 등으로 불린다. 이 성질을 이용하면 비교 정렬의 최소 [[시간 복잡도]]를 알 수 있다. 우선 정렬하고자 하는 유한집합 [math(A')]이 전순서 집합 [math(A)]의 크기가 [math(|A'|=n)]인 부분집합일 때, 모든 원소가 서로 다르므로 가능한 [[순열]]의 개수는 [math(_n{\rm P}_n=n!)]이며 이중 단 하나만이 올바른 정렬 결과일 것이다. 임의의 [math(a)]와 [math(b)]의 비교는 [[이항 관계|이항 연산]]이므로 올바른 정렬을 찾기 위한 비교 연산의 최소 횟수는 [[2의 거듭제곱]]으로 늘어난다. 따라서 정렬이 적어도 [math(f(n))]번 안에 끝난다면 결정 트리의 최대 폭은 [math(2^{f(n)})]이 되며 검증해야 하는 최대 조합 수는 [math(n!)]이므로, {{{#!wiki style="text-align: center" [math(2^{f(n)}\ge n!\Rightarrow f(n)\ge\operatorname{lb}n!)]}}} 이제 [[스털링 근사]]를 사용해 [math(n!)]을 근사하면 {{{#!wiki style="text-align: center" [math(\operatorname{lb}n!\ge\operatorname{lb}\left(\dfrac n2\right)^{\frac n2}=\dfrac n2\operatorname{lb}\dfrac n2=\dfrac n2\Bigl(\operatorname{lb}n-\operatorname{lb}2\Bigr)=\dfrac n2\operatorname{lb}n-\dfrac n2\approx\mathcal O(n\log n))]}}} 비교 연산의 실행 횟수 [math(f(n))]의 하한이 [math(n\log n)]에 근사하므로 모든 비교 정렬 알고리즘은 아무리 빨라도 [math(\mathcal O(n\log n))] 보다 빠를 수 없음을 알 수 있다. 비비교 정렬의 경우 특수한 환경에서 [math(\mathcal O(n\log n))]보다 빠른 효율을 보이기도 하지만, 일반적으로 적용되기에는 비교 정렬에 비해 여러 제약이 존재한다. 예를 들어 대표적인 비비교 정렬 중 하나인 [[정렬 알고리즘#s-4.4.2|계수 정렬]](counting sort)의 경우, [math(\mathcal O(n))]이라는 매우 빠른 속도를 가지지만 유한한 범위의 양의 정수[* 범위가 유한하다면 적절한 처리를 통해 음수도 가능하다.] 집합에서만 성립한다. 실수의 경우 항상 두 실수 사이에 무한한 실수가 존재할 수 있어 인덱싱이 의미가 없기 때문이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기