비교 기반 정렬 기술의 제한

Question

비교 정렬은 데이터를 정렬해야하는 대부분의 시나리오에서 선택됩니다. 병합 정렬, 빠른 정렬, 삽입 정렬 및 기타 비교 정렬과 같은 기술은 O (nLog (n))의 하한으로 다른 데이터 유형 및 효율성을 처리 할 수 ​​있습니다.

내 질문은 기술을 분류 기준으로 비교의 제한이

1. 입니까?
2. 비 비교 정렬 기법이 사용되는 시나리오는 어떤 종류입니까?

환호

Answer 1

당신은 더 많거나 적게 자신을 대답했다. 비교 기반 정렬 기법은 O (n Log (n))의 하한으로 제한됩니다. 비 비교 기반 정렬 기법은이 한계를 겪지 않습니다. 비 정렬 알고리즘의 일반적인 문제점은 도메인이 더 잘 알려 져야한다는 것이므로 비교 기반 기술만큼 다용도 적이 지 않다는 것입니다.

Pigeonhole sort은 가능한 키 값 수가 요소 수에 매우 가깝다면 꽤 빠릅니다.

Answer 2

분명히 비교 유형의 제한은 시간 계수 -some are better than others이지만 충분히 큰 데이터 세트가 주어지면 어느 시점에서 너무 느려질 것입니다. 트릭은 정렬하는 데이터의 종류와 혼합을 고려하여 올바른 것을 선택하는 것입니다.

비 비교 정렬은 데이터를 무시하는 다른 요소를 기반으로합니다. 예 : counting sort은 각 요소를 검사하여 데이터 집합을 정렬합니다 (컬렉션의 다른 값과 비교하지 않음). 소트를 계산하는 것은 어떤 데이터를 기반으로 콜렉션을 정렬하는 데 유용합니다. 정수의 콜렉션을 가지고 있다면, 값이 1 인 모든 요소를 ​​취해 목적지에 먼저 넣은 다음 값 2의 모든 요소를 ​​순서대로 정렬합니다. (좋아, 그것은 "스파 스"배열을 사용하여 신속하게 컬렉션을 확대/축소하고 값을 재정렬하지만 간격은 남겨 둡니다. 기본 원리입니다.)

Answer 3

비교 정렬에 N 로그 N 비교가 필요한 이유는 쉽게 알 수 있습니다. N이 있습니다! 순열과 우리가 알고 있듯이 ln (N!)은 대략 Nln N - N + O (ln N)이다. Big O 표기법에서는 N ln N보다 낮은 항을 무시할 수 있으며 ln과 log가 상수 만 다른 경우 최종 결과 O (N log N)