Bucket Sort Integers

vckicks 0 Tallied Votes 2K Views Share

Bucket sort is a very simple, fast sorting algorithm specialized in integers.

public void BucketSort(int[] integers)
        {
            //Verify input
            if (integers == null || integers.Length == 0)
                return;

            //Find the maximum and minimum values in the array
            int maxValue = integers[0]; //start with first element
            int minValue = integers[0];

            //Note: start from index 1
            for (int i = 1; i < integers.Length; i++)
            {
                if (integers[i] > maxValue)
                    maxValue = integers[i];

                if (integers[i] < minValue)
                    minValue = integers[i];
            }

            //Create a temporary "bucket" to store the values in order
            //each value will be stored in its corresponding index
            //scooting everything over to the left as much as possible (minValue)
            //e.g. 34 => index at 34 - minValue
            List<int>[] bucket = new List<int>[maxValue - minValue + 1];

            //Initialize the bucket
            for (int i = 0; i < bucket.Length; i++)
            {
                bucket[i] = new List<int>();
            }

            //Move items to bucket
            for (int i = 0; i < integers.Length; i++)
            {
                bucket[integers[i] - minValue].Add(integers[i]);
            }

            //Move items in the bucket back to the original array in order
            int k = 0; //index for original array
            for (int i = 0; i < bucket.Length; i++)
            {
                if (bucket[i].Count > 0)
                {
                    for (int j = 0; j < bucket[i].Count; j++)
                    {
                        integers[k] = bucket[i][j];
                        k++;
                    }
                }
            }
        }

Dani AI

Generated

Nice, — the posted routine is a clear bucket/counting-style approach: it finds min/max, allocates one bucket per integer value (index = value - min), pushes values into those buckets, then flattens them back. That offset makes the method work with negative numbers and, because each bucket is appended in input order, the result is stable. Time and space are both O(n + k) where k = maxValue - minValue + 1, so performance is excellent when k is small but can be terrible (memory and speed) when k is large.

A small, faster variant for dense ranges is counting sort: use a single int[] of counts (no per-bucket List overhead), then write values back. This is safe and compact for moderate ranges:

public static void CountingSort(int[] a)
{
    if (a == null || a.Length == 0) return;
    int min = a[0], max = a[0];
    for (int i = 1; i < a.Length; i++)
    {
        if (a[i] < min) min = a[i];
        else if (a[i] > max) max = a[i];
    }
    long range = (long)max - min + 1;
    if (range > int.MaxValue) throw new ArgumentException("Range too large.");
    int[] counts = new int[(int)range];
    for (int i = 0; i < a.Length; i++) counts[a[i] - min]++;
    int k = 0;
    for (int i = 0; i < counts.Length; i++)
        for (int c = 0; c < counts[i]; c++) a[k++] = i + min;
}

Notes and tradeoffs: for very sparse or enormous ranges use a hash map (count only present keys) plus sorting of keys, or fall back to a comparison sort (O(n log n)). Radix sort is another O(n) option for large integer domains. As suggested, benchmark different inputs (random, sorted, reverse, sparse) with System.Diagnostics.Stopwatch to choose the right variant for a given workload. Thanks to for the implementation and to for testing it out.

ddanbe 2,724 Professional Procrastinator Featured Poster

Nice!
Have you read http://www.daniweb.com/code/snippet979.html?
Maybe you can test wich of the three is the fastest?

MosaicFuneral 812 Nearly a Posting Virtuoso

Interesting, I'll try this out.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.