バケットソートでは、整列したい配列の要素の値をインデックス番号として新しい配列（バケット）に代入して、そのあとバケットの先頭から拡張を取り出して整列するアルゴリズムである。例えば 0 から 99 までの整数からなる配列 A を整列させるとき、100 個の要素を持つ配列 B （バケット）を用意する。次に、例えば A[1] が 12 ならば、B[12] に A[1] を代入するなどのように、A の各要素の値をインデックス番号として、配列 B に代入する。ただ、重複した値が存在する場合があるので、配列の B の各要素は後から追加できるようなベクターあるいはリストとする必要がある。

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


void bucketSort(int array[], int array_size) {

    // calculate bucket size
    int bucket_size = array[0];
    for(int i = 1; i < array_size; i++) {
        if(array[i] > bucket_size) {
            bucket_size = array[i];
        }
    }
    bucket_size += 1;

    // create empty buckets
    std::vector<int> bucket[bucket_size];

    // put array elements into buckets depending on the value
    for (int i = 0; i < array_size; i++) {
        bucket[array[i]].push_back(array[i]);
    }

    // sort individual buckets, if needed
    // for (int i = 0; i < bucket_size; i++) {
    //    sort(bucket[i].begin(), bucket[i].end());
    //}

    // concatenate all buckets into array
    int id = 0;
    for (int i = 0; i < bucket_size; i++) {
        for (int j = 0; j < bucket[i].size(); j++) {
            array[id++] = bucket[i][j];
        }
    }
}


int main (void) {

    int i;
    int array[] = {3, 0, 11, 14, 2, 0, 32, 35, 39, 8, 9, 10};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    bucketSort(array, sizeof(array) / sizeof(array[0]));

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}