Bucket sort

【 notes 】 Refer to the textbook 「 Introduction to algorithms 」.

1. brief introduction

  Bucket sorting is to divide the sequence to be sorted into a limited number of buckets , Then sort each bucket separately . The premise of bucket sorting is that the keyword values of the sorted sequence conform to uniform distribution , At this time, the average time complexity of bucket sorting is O(n + {n^2 \over k} + k), The worst time complexity is O(n^2), among k For the number of barrels . When the number of barrels k \approx n when , At this point, the complexity of bucket sorting is linear O(n) .

  The order of barrels is Non original , Its The stability depends on the stability of the inner ordering . Generally, stable insertion sort is used as the inner sort algorithm , At this time, the bucket sorting is stable .

2. thought

The main idea of bucket sorting is to block the key values of the sorting sequence , Each piece corresponds to a barrel , Then use insert sort for each bucket （ Or other sorting algorithms ） Sort , Finally, all the elements in the bucket are connected in series to get an ordered sequence .

3. Realization

3.1 Pseudo code

BucketSort(A, mx, n) {
    // mx  Is the maximum value ,n  Is the number of barrels 
    //  Definition  n  A barrel 
    define bucket[n]
    //  Calculate the block size of the block 
    bucketsize = mx/n + 1
    //  It is divided into blocks according to the sorting key values of the elements 
    for i = 1 to A.length
        bucket[A[i]/bucketsize].PushBack(A[i])
    for i = 0 to n-1
        InsertSort(bucket[i])
    cnt = 0
    for i = 0 to n-1
        for j = 1 to bucket[i].length
            A[++cnt] = bucket[i][j]
}

3.2 Templates

#include <bits/stdc++.h>
using namespace std;

#ifndef _BUCKET_
#define _BUCKET_
#define ll int
#define MAXN 100005
#define MAXBUK 1000
#define INF 10000000

//  Bucket sort 
template < typename T >
struct Bucket {
    vector < pair<T, ll> > bucket[MAXN];
    Bucket() {}
    //  Insertion sort 
    void insertSort(vector < pair<T, ll> > & bkt) {
        for(ll i = 1; i < bkt.size(); ++i) {
            pair <T, ll> key = bkt[i];
            ll j = i - 1;
            while(~j && bkt[j].second > key.second) {
                bkt[j+1] = bkt[j];
                j--;
            }
            bkt[j+1] = key;
        }
    }
    //  Bucket sort 
    void bucketSort(T *bA, T *eA, ll *bK, ll *eK, ll mx = INF, ll bn = MAXBUK) {
        ll len_A = eA - bA;
        ll len_K = eK - bK;
        T *A = bA;
        ll *K = bK;
        ll bucketsize = mx/bn + 1;
        //  Judge whether the size of keyword array matches the size of element array 
        assert(len_A == len_K);
        //  Initialize bucket 
        for(ll i = 0; i < bn; ++i) {
            bucket[i].clear();
        }
        //  Put the elements in the bucket 
        for(ll i = 0; i < len_K; ++i) {
            bucket[K[i]/bucketsize].push_back(pair<T, ll>{A[i], K[i]});
        }
        //  Insert sorting for each bucket 
        ll cnt = 0;
        for(ll i = 0; i < bn; ++i) {
            insertSort(bucket[i]);
            for(ll j = 0; j < bucket[i].size(); ++j) {
                A[cnt++] = bucket[i][j].first;
            }
        }

    }
};
#endif