버킷 정렬과 기수 정렬의 차이점은 무엇입니까?

Question

버킷 정렬 및 기수 정렬은 가까운 사촌입니다. 버킷 정렬은 MSD에서 LSD로 진행되는 반면, 기수 정렬은 "방향"(LSD 또는 MSD)에서 모두 수행 될 수 있습니다. 두 알고리즘은 어떻게 작동합니까? 특히 어떻게 다릅니 까?

Answer 1

RadixSort과 BucketSort의 초기 패스는 완전히 동일합니다. 요소는 최대 숫자의 자릿수에 따라 buckets (또는 bins)의 증분 범위 (예 : 0-10, 11-20, ... 90-100)에 배치됩니다.

그러나 다음 패스에서 BucketSort은 이러한 '버킷'을 주문하고 하나의 배열에 추가합니다. 그러나 RadixSort은 더 이상 정렬하지 않고 버킷을 추가하고 숫자의 두 번째 숫자 (10 자리)를 기반으로 '다시 버킷'합니다. 그러므로 BucketSort는 'Dense'배열에 대해보다 효율적이며, RadixSort는 희소 배열을 잘 처리 할 수 ​​있지만 잘 배열되지는 않습니다.

Answer 2

버킷 정렬 및 기수 정렬은 비교 정렬이 아니며 일반적인 아이디어가 비슷하기 때문에 자매 정렬 알고리즘과 같습니다. 또한, 둘 다 구현이 조금 추상적입니다.

기수 정렬 :

• 기수 베이스 (진 등, 8 진수 소수)을 의미한다. 따라서이 정렬은 숫자 (문자열에도 사용됨)에 대한 것입니다. 각각의 요소 E가 E _I 일부 범위 인 E K ... _{2 E E E 1 0 같아서 때 작동한다. (일반적으로 0 ASCII 문자의 진수 0-9 또는 255 같은베이스)}

• 그것은 다음 은 또는 다른 기수 정렬 원 안정적이어야한다 (안정된 서브 정렬 알고리즘의 K 패스를 사용 '일하지 마라'). 이 하위 정렬 알고리즘은 보통 대용량 정렬 또는 버킷 정렬이기도하지만 자체는 기수 정렬 일 수 없습니다.

• 당신이 (K K가 0 또는 0), 각 패스마다 번호을 섞어 때문에 상위 자리 또는 최하위 디지트

• 그것이 안정 정렬 알고리즘에서 시작할 수

  .

버킷 정렬은 :

• 은 작은 그룹 또는 버킷으로 배열을 분리하고 개별적으로 자체 하위 분류 알고리즘 또는 재귀 호출을 사용하여 정렬 한 후 그 결과를 결합. 예를 들어, 팀의 버킷을 추가하고 저지 번호 또는 1에서 30 사이의 숫자를 1-10, 11-20, 21-30의 3 버켓으로 정렬하여 정렬하여 플레이어를 정렬합니다.

• 결합 단계는 보통 (병합 정렬과 다름)입니다.다만

가

• 기수/염기 군/버킷 타입/인스턴스 될 수 다시 원래의 배열로 각 버킷의 요소를 복사하거나 (링크드리스트의 경우) 이전 버킷 꼬리 각 버킷의 선두 합류 동시에 번호를 정렬합니다. 따라서 당신은 자리에서하지만 안정적인 정렬 알고리즘 정렬되지

• 버킷 종류의 버킷의 수정 된 인스턴스로 MSD 기수 생각할 수있다. 그러나 버킷 정렬의 일부 변형은 안정적이지 않을 수 있습니다 (안정되지 않은 하위 정렬 알고리즘을 사용하는 경우)