4
$\begingroup$

Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don't need to be sorted.

For example, for the input

[64, 72, 57, 47, 5, 4, 64, 21, 64, 65, 36, 43, 81, 44, 19, 87, 17, 86, 
 73, 21, 19, 64, 94, 91, 34, 49, 8, 52, 18, 37]

that I want to divide into 5 buckets, some valid outputs would be

[[4, 5, 8, 17, 18], [19, 19, 21, 21, 34], [36, 37, 43, 44, 47], 
 [49, 52, 57, 64, 64], [64, 64, 65, 72, 73]]

[[8, 17, 18, 5, 4], [21, 19, 21, 34, 19], [43, 37, 44, 36, 47], 
 [52, 57, 49, 64, 64], [64, 64, 72, 73, 65]]

[[8, 18, 5, 4, 17], [19, 19, 21, 21, 34], [47, 36, 44, 43, 37], 
 [52, 64, 49, 64, 57], [64, 72, 64, 65, 73]]

[[18, 8, 17, 5, 4], [21, 19, 21, 19, 34], [36, 44, 43, 37, 47], 
 [57, 64, 64, 49, 52], [64, 72, 64, 65, 73]]

One approach to do this would be to sort the list, and then divide it at equal intervals. Can this be done faster?

I would also be happy with a result where the buckets are of only roughly equal size, but note that I can't assume a uniform distribution for the numbers, so bucket sort doesn't help.

$\endgroup$
4
$\begingroup$

Assuming you want to create $k$ buckets, to the following.

  1. Obtain elements of rank $\lceil n/k \rceil, 2 \cdot \lceil n/k \rceil \dots, (k-1) \cdot \lceil n/k \rceil$.
  2. Perform multi-way partitioning (cf. Quicksort) with these elements as pivot.

Both steps take time $\Theta(kn)$. All buckets are within $\pm 1$ of the same size.

In the case of duplicate elements, you can "uniquify" them in a $\Theta(n)$ preprocessing run; otherwise bucket sizes might differ more.

Essentially, this is performing only the top-level call of a $k$-way Quicksort with perfect pivots. All variants regarding pivot selection and partitioning apply and will lead to different runtime and bucket size characteristics.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Just thought of this off the top of my head. You could try to use a B+ tree, with number of pointers $m=k$, where $k$ is your bucket size.

The leaves would be your partitioned buckets. If you went from the list to the B+ tree, then each insert is $O(log_k(n))$ and for n items, it would take $O(n*log_k(n))$ for inserting the entire list. If you are using a B+ tree you happen to have direct access to the B+ structure, you could just collect the pointer to the leaf nodes.

You could also just get rid of the list altogether sacrificing a $O(1)$ insertion to have the buckets already created for you in the B+ tree in $O(1)$.

One down side, is that the buckets may not be full, but they will be partially ordered.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How does that beat sorting and splitting? Same (asymptotic) runtime. $\endgroup$ – Raphael Aug 6 '14 at 20:57

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.