버킷 정렬 계산기

값이 나올 것으로 가정한 범위를 버킷 개수만큼 같은 폭으로 나누고, 각 원소를 자기 값이 속한 버킷에 담습니다. 그다음 버킷 «안»을 삽입정렬하고, 버킷을 순서대로 이어붙이면 전체가 정렬됩니다.

입력이 범위 안에 고르게 퍼져 있다는 전제 아래에서는 버킷 하나에 원소가 몇 개(평균 n/k개) 없을 것으로 기대하기 때문입니다. 원소 수가 적을 때는 삽입정렬이 오버헤드가 작아 오히려 효율적입니다.

이 식은 입력이 가정한 범위 안에 고르게(균등분포로) 퍼져 있다는 전제에서만 성립합니다. 실제 값이 범위의 일부에만 몰리면 그 버킷 하나에 원소가 잔뜩 쌓이고, 버킷 안 삽입정렬이 O(m²)까지 늘어납니다. 극단적으로 모든 값이 한 버킷에 몰리면 사실상 전체를 삽입정렬한 것과 같아져 O(n²)가 됩니다.

범위를 입력의 최솟값·최댓값으로 자동으로 잡으면 버킷이 항상 고르게 채워지는 것처럼 보이는 착시가 생깁니다. 실제 알고리즘을 쓸 때는 미래에 들어올 값의 범위를 미리 가정해 버킷을 만들어 두는 것이 보통이라, 가정한 범위와 실제 데이터 분포가 어긋나면 성능이 나빠지는 것을 이 계산기에서 직접 확인할 수 있습니다.

셋 다 비교 없이 값의 성질을 이용한 선형시간 근처 정렬이지만 전제가 다릅니다. 카운팅 정렬은 값의 «범위(k)»가 작은 정수에 적합하고, 기수 정렬은 자릿수별로 반복해 큰 정수나 문자열에 적합합니다. 버킷 정렬은 값이 실수든 정수든 «범위 안에 고르게 퍼져 있을 때» 유리하며, 버킷 안에서는 여전히 비교 기반 정렬(삽입정렬)을 씁니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.