나는 다른 게시물에서이 주석을 읽었으며 별도의 질문을 열었습니다 :
Bucket sort는 'Dense'배열에 대해 더 효율적입니다. Radix Sort는 스파 스 (물론 정확하게는 스파 스가 아니라 간격이 좁은) 배열을 잘 나타냅니다.
이것이 어떻게 그렇게 이해할 수 있습니까?
내가 이해하는 한, 인구의 '밀도'는 두 알고리즘 모두에 대해 균등하게 버킷의 수에 영향을 미칩니다.
또한 삽입 정렬 (각 버킷에서)은 밀도에 큰 영향을받지 않습니다 - 그렇지 않습니까?Bucket vs Radix sort
"고밀도"대 "이격 형"의 구별은 정렬되는 데이터의 분포의 균일 성에 달려 있다고 생각합니다. 균일하게 분산 된 데이터는 "고밀도"로 간주됩니다.
버킷 정렬은 숫자 값의 위쪽 부분을 기준으로 입력을 버킷으로 분할하므로 균일 분포를 갖는 입력은 각 버킷에 멋진 짧은 목록을 형성합니다. 반대로 큰 갭을 가진 입력은 많은 빈리스트를 형성 할 것이고, 긴리스트는 원래 입력과 길이면에서 비교 될 수있다. 이것은 "분산 형"단계가 원래 문제를 그다지 줄이지 않기 때문에 개별 버킷을 정렬하는 기수 정렬의 중간 단계에 나쁜 소식입니다.
반면에 기수 정렬은 입력의 숫자 분포에 신경을 쓰지 않습니다. 알고리즘은 가장 큰 구성원의 동일한 크기 및 자릿수의 입력에 대해 동일한 시간을 사용합니다. 각 "숫자"에 대한 단계는 정확히 O(N) 단계를 취합니다. 일단 가장 중요한 자릿수를 입력하면 작업이 완료됩니다. 정렬되는 값의 분포는 알고리즘의 타이밍으로 재생되지 않습니다.
같은 버킷으로 끝나는 요소의 수를 언급하는 'sparse'및 'dense'라고 생각합니다.
예를 들어 10 개의 버킷을 사용하여 0에서 999 사이의 숫자를 정렬하면 첫 번째 버킷은 [0-99]이고 두 번째는 [100-199]입니다.
거의 모든 값이 100보다 작은 경우 모두 동일한 버킷으로 끝납니다. 이 경우 버킷 정렬은 개별 버킷 (삽입 정렬 일 수 있음)을 정렬하는 알고리즘만큼 느립니다.
Radix sort는 버킷을 정렬, 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하지만, 단지 개별적으로 각 자리에 버킷 종류의 일종을 적용하지 않습니다. 기수 정렬의 경우, 동일한 양동이에 얼마나 많은 요소가 들어갈 것인지는 관계가 없습니다.
후자의 예제를 추가하려면 [711, 411, 611, 911, 211]을 정렬하려고한다고 가정 해 봅시다. 최하위 숫자를 정렬하면 모든 요소가 동일한 버킷에 배치됩니다 (순서는 변경되지 않음). 두 번째 중요한 자릿수를 정렬하면 똑같이 처리됩니다. 최상위 자릿수가 정렬 될 때만 요소가 다른 버킷에 배치됩니다. 성능에 미치는 영향은 없습니다.