Bucket sort

Ten values between 0 and 1, and ten buckets: 0.42 goes in bucket 4, 0.07 in bucket 0. Watch how little sorting is left once each value is in its bucket.

⋯7struct dnode {8    double value;9    struct dnode *next;10};11 12void bucket_sort(double *a, int n)13{14    struct dnode *bucket[BUCKETS] = { NULL };15    for (int i = 0; i < n; i++) {16        struct dnode *x = malloc(sizeof *x);17        if (x == NULL)18            exit(1);19        x->value = a[i];20        struct dnode **link = &bucket[(int)(a[i] * BUCKETS)];21        while (*link != NULL && (*link)->value <= x->value)22            link = &(*link)->next;23        x->next = *link;24        *link = x;25    }26    int k = 0;27    for (int b = 0; b < BUCKETS; b++) {28        struct dnode *p = bucket[b];29        while (p != NULL) {30            struct dnode *next = p->next;31            a[k++] = p->value;32            free(p);33            p = next;34        }35    }36}

Buckets, chains and the average

For values in [0, 1) and n buckets, value v goes in bucket ⌊n·v⌋: with ten buckets, its first digit after the point. Bucket 0 takes [0, 0.1), bucket 1 [0.1, 0.2), and so on, so every value in bucket b is smaller than every value in bucket b + 1. Sort each bucket, read the buckets out in order, and the whole array is sorted.

Each bucket here is a linked list, a chain, kept sorted as values arrive: a new node is inserted after the values that are not larger than it, as in insertion sort.

If the values are spread evenly, each bucket gets about one value on average, and the insertions cost almost nothing. Dropping n values in and reading them out is then O(n) expected time. If the values bunch, one bucket gets them all, and its chain is an insertion sort of n values: O(n²).

The code and its cost

struct dnode {
    double value;
    struct dnode *next;
};

void bucket_sort(double *a, int n)
{
    struct dnode *bucket[BUCKETS] = { NULL };
    for (int i = 0; i < n; i++) {
        struct dnode *x = malloc(sizeof *x);
        if (x == NULL)
            exit(1);
        x->value = a[i];
        struct dnode **link = &bucket[(int)(a[i] * BUCKETS)];
        while (*link != NULL && (*link)->value <= x->value)
            link = &(*link)->next;
        x->next = *link;
        *link = x;
    }
    int k = 0;
    for (int b = 0; b < BUCKETS; b++) {
        struct dnode *p = bucket[b];
        while (p != NULL) {
            struct dnode *next = p->next;
            a[k++] = p->value;
            free(p);
            p = next;
        }
    }
}

link is a pointer to a link: first the address of the bucket’s head, then the address of a node’s next. The while moves it past the values that are not larger than x, and the last two lines splice x in where link points, whether that is the head, the middle or the end of the chain. This is the same pointer to a link as in Removing from a linked list.

The test <= puts a new value after equal ones, so equal values keep their input order.

The ten values

Buckets 2, 3 and 7 stay empty. buckets.c prints 0.03 0.07 0.15 0.42 0.44 0.48 0.56 0.61 0.88 0.93. Only two values had to step past another in their chain: 0.48 past 0.42, and later 0.44 past 0.42.

One detail of floating point: 0.07 × 10 is 0.7000000000000001 in a double, not 0.7, but (int) cuts it down to 0 all the same.

Worked example

Bunched values. Ten values all between 0.40 and 0.50 land in bucket 4. In ascending order each new value walks the whole chain: 0 + 1 + … + 9 = 45 comparisons, the worst case of insertion sort. bunched.c counts the value comparisons in the while: spread: 4 comparisons for the ten values above, bunched, ascending: 45 comparisons for 0.40, 0.41, …, 0.49.

Values from 0 to 1,000. Divide each by 1,001, one more than the largest possible value, before multiplying by the number of buckets. Dividing by 1,000 would send the value 1,000 to bucket ⌊n · 1⌋ = n, one past the last bucket.

Two checks. Which bucket does 0.999 go in? (9.) Which input makes bucket sort slow? (Values bunched in one bucket.)

Where it’s used

Values known to be spread evenly, such as random numbers or hash values.

Histograms, which are the first half of bucket sort: drop values into ranges and count them.

Hash tables with chaining use the same chains, but to find a key rather than to sort (Hash tables with chaining).

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, double 8, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.