3
$\begingroup$

Wikipedia has this pseudocode on bucket sort:

function bucketSort(array, n) is buckets ← new array of n empty lists for i = 0 to (length(array)-1) do insert array[i] into buckets[msbits(array[i], k)] for i = 0 to n - 1 do nextSort(buckets[i]); return the concatenation of buckets[0], ...., buckets[n-1]

It also explains:

Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets...

What baffles me is: Why would one want to initialize buckets with n buckets when 2^k is the maximum number of values that msbits can possibly generate, given the way it's defined?

$\endgroup$
3
$\begingroup$

The code you found is unfortunately written and explained in a very confusing way, most notably in a way that, in my humble opinion, misses the entire point of Bucketsort.

Let $A$ be an array of $n$ elements, taken from the ordered set $(S, \le)$. Bucketsort is a sorting algorithm that sorts $A$ in linear time with probability $1$, subject to the hypothesis that the statistical distribution of the elements of $A$ over $S$ is known in advance.

For the sake of simplicity, we will assume $S$ to be the real interval $[0, 1)$ and the distribution of $A$ to be uniform over $[0, 1)$. Our second assumption is without loss of generality. In fact, should we be provided with a different probability density function $\rho$, we could simply replace each $x \in A$ with:

$$ x' =\int_{0}^x \rho(z) dz $$

An analogous argument holds for different choices of $S$.

Bucketsort works as follows:

  • Split $[0, 1)$ in $n$ consecutive intervals, where $n = |A|$, such that the $i$-th interval is $\left[ \frac{i-1}{n}, \frac{i}{n} \right)$
  • Create $n$ empty lists $L_1, L_2, \dots, L_n$
  • For each element $x$ of $A$, add $x$ to the list corresponding to the interval in which it falls
  • Sort each list individually, then return the concatenation $L_1 \circ L_2 \circ \dots \circ L_n$

Correctness is obvious, but complexity isn't. The crucial hypothesis is that, by assumption, we are sorting elements uniformly distributed over $[0, 1)$. Therefore, if $n$ grows large, as it is the case in the usual asymptotic setting, at the end of our third step, each of the lists will contain a constant number of elements with probability $1$; if that weren't the case, the elements wouldn't be uniformly distributed after all. Also observe that "with probability $1$" is not the same as "certainly", although it's as close as it gets.

The choice of exactly $n$ buckets is due to the fact that we want our last step to take linear time; but that can only be achieved if each list contains a constant amount of elements. We could have chosen just as well to use $n/c$ buckets for any $c \in \Theta(1)$, but we couldn't have started with $ k \in o(n)$ buckets; each of them would have contained $n/k \in \omega(1)$ elements. The total cost of sorting them would have been:

$$ k \left ( \frac{n}{k} \log \frac{n}{k} \right ) = n \log \omega(1) \in \omega(n) $$

$\endgroup$
  • $\begingroup$ I'm grateful for your in-depth and knowledgeable response. It probably contains the answer I'm looking for, but, unfortunately, I lack sufficient math background to follow it. $\endgroup$ – Julian A. Feb 11 '17 at 19:00
  • $\begingroup$ @Julian Is there anything in particular you are having problems with? I can try to clear it up. $\endgroup$ – quicksort Feb 11 '17 at 20:06
1
$\begingroup$

Yes, msbits(x, k) can generate up to 2^k values. But this does not mean buckets[] array has to be length of 2^k. If buckets[] has length 2^k, each bucket has size one, and bucket sort degenerates into counting sort.

So, you want each bucket size to be more than 1. If we have n buckets, and msbits(x, k) returns 2^k values, then each bucket size is 2^k/n.

On the contrary, if we choose n = 1, then we will only have one bucket of 2^k. If we choose another sorting algorithm to this bucket, then our bucket sort will have the same order of growth as the chosen sorting algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.