Bucket sort

Summary

This chapter introduces bucket sorting in sorting algorithm . The content includes ：
1.  Introduction to bucket sorting
2.  Bucket sorting graphic description
3.  Bucket sorting implementation
3.1   Bucket sort C Realization
3.2   Bucket sort C++ Realization
3.3   Bucket sort Java Realization

Reprint please indicate the source ： Bucket sort - If the sky doesn't die - Blog Garden

---

For more sorting and algorithms, please refer to ： Data structure and algorithm series Catalog

Introduction to bucket sorting

Bucket sort (Bucket Sort) It's very simple , It divides the array into a limited number of buckets .

Suppose the array to be sorted a The Communist Party of China has N It's an integer , And the array is known a Range of data in [0, MAX). When sorting buckets , Create a capacity of MAX Bucket array r, And initialize the bucket array elements to 0; The capacity will be MAX Each cell in the bucket array is treated as a " bucket ".
When sorting , Traverse the array one by one a, Will array a Value , As " Bucket array r" The subscript . When a When data in is read , Just add the value of the bucket 1. for example , Read array a[3]=5, Will r[5] Value +1.

Bucket sorting graphic description

Bucket sort code

/*
 *  Bucket sort 
 *
 *  Parameter description ：
 *     a --  Sorted array 
 *     n --  Array a The length of 
 *     max --  Array a The range of the maximum in 
 */
void bucketSort(int a[], int n, int max)
{
    int i,j;
    int buckets[max];

    //  take buckets All data in is initialized to 0.
    memset(buckets, 0, max*sizeof(int));

    // 1.  Count 
    for(i = 0; i < n; i++) 
        buckets[a[i]]++; 

    // 2.  Sort 
    for (i = 0, j = 0; i < max; i++) 
    {
        while( (buckets[i]--) >0 )
            a[j++] = i;
    }
}

bucketSort(a, n, max) Yes to array a Sort the buckets ,n It's an array a The length of ,max Is the range of the largest element in the array [0,max).

hypothesis a={8,2,3,4,3,6,6,3,9}, max=10. here , Will array a All the data in need is 0-9 The barrels . Here's the picture ：

After putting the data into the bucket , Then through a certain algorithm , Bring out the data in the bucket and convert it into an ordered array . We get the result we want .

Bucket sorting implementation

Bucket sort C Realization
Implementation code (bucket_sort.c)

/**
 *  Bucket sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/13
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )

/*
 *  Bucket sort 
 *
 *  Parameter description ：
 *     a --  Sorted array 
 *     n --  Array a The length of 
 *     max --  Array a The range of the maximum in 
 */
void bucket_sort(int a[], int n, int max)
{
    int i, j;
    int *buckets;

    if (a==NULL || n<1 || max<1)
        return ;

    //  Create a capacity of max Array of buckets, And will buckets All data in is initialized to 0.
    if ((buckets=(int *)malloc(max*sizeof(int)))==NULL)
        return ;
    memset(buckets, 0, max*sizeof(int));

    // 1.  Count 
    for(i = 0; i < n; i++)
        buckets[a[i]]++;

    // 2.  Sort 
    for (i = 0, j = 0; i < max; i++)
        while( (buckets[i]--) >0 )
            a[j++] = i;

    free(buckets);
}

void main()
{
    int i;
    int a[] = {8,2,3,4,3,6,6,3,9};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    bucket_sort(a, ilen, 10); //  Bucket sort 

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Bucket sort C++ Realization
Implementation code (BucketSort.cpp)

/**
 *  Bucket sort ：C++
 *
 * @author skywang
 * @date 2014/03/13
 */

#include <iostream>
#include <cstring>
using namespace std;

/*
 *  Bucket sort 
 *
 *  Parameter description ：
 *     a --  Sorted array 
 *     n --  Array a The length of 
 *     max --  Array a The range of the maximum in 
 */
void bucketSort(int* a, int n, int max)
{
    int i, j;
    int *buckets;

    if (a==NULL || n<1 || max<1)
        return ;

    //  Create a capacity of max Array of buckets, And will buckets All data in is initialized to 0.
    if ((buckets = new int[max])==NULL)
        return ;
    memset(buckets, 0, max*sizeof(int));

    // 1.  Count 
    for(i = 0; i < n; i++)
        buckets[a[i]]++;

    // 2.  Sort 
    for (i = 0, j = 0; i < max; i++)
        while( (buckets[i]--) >0 )
            a[j++] = i;

    delete[] buckets;
}


int main()
{
    int i;
    int a[] = {8,2,3,4,3,6,6,3,9};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    bucketSort(a, ilen, 10); //  Bucket sort 

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Bucket sort Java Realization
Implementation code (BucketSort.java)

/**
 *  Bucket sort ：Java
 *
 * @author skywang
 * @date 2014/03/13
 */

public class BucketSort {

    /*
     *  Bucket sort 
     *
     *  Parameter description ：
     *     a --  Sorted array 
     *     max --  Array a The range of the maximum in 
     */
    public static void bucketSort(int[] a, int max) {
        int[] buckets;

        if (a==null || max<1)
            return ;

        //  Create a capacity of max Array of buckets, And will buckets All data in is initialized to 0.
        buckets = new int[max];

        // 1.  Count 
        for(int i = 0; i < a.length; i++)
            buckets[a[i]]++;

        // 2.  Sort 
        for (int i = 0, j = 0; i < max; i++) {
            while( (buckets[i]--) >0 ) {
                a[j++] = i;
            }
        }

        buckets = null;
    }

    public static void main(String[] args) {
        int i;
        int a[] = {8,2,3,4,3,6,6,3,9};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        bucketSort(a, 10); //  Bucket sort 

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

above 3 The principle and output of the two implementations are the same . Here is their output ：

before sort:8 2 3 4 3 6 6 3 9 
after  sort:2 3 3 3 4 6 6 8 9