# Example of a method for implementing bucket sorting in C language

• 2020-06-01 10:28:33
• OfStack

This article demonstrates an example of how the C language implements bucket sorting. I will share it with you for your reference as follows:

Definition 1.

Assume: the input is a real number evenly distributed on the interval [0, 1] generated by a random process. Divide the interval [0, 1] into n subintervals (buckets) of equal size, with the size of 1/n: [0, 1/n), [1/n, 2/n), [2/n, 3/n),... [k/n, (k+1)/n), [k/n, (k+1)/n),... < The 1 auxiliary array B[0.. n-1] is an array of 1 Pointers to buckets (linked lists).

2. The performance

For N data to be sorted and M data to be sorted, the average bucket sorting time complexity of each bucket [N/M] data is:

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

The time complexity of quicksort is n*log2(n)

When N=M, that is, when there is only 1 data per bucket in the limit case. The best efficiency of bucket sorting is O(N).

Bucket sorting is stable

3. The implementation

``````
/*==============================
8 name:bucket sort
--------------------------------
time complexity:
average
O(n+nlogn-nlogm)
--------------------------------
space complexity:
O(n)
--------------------------------
stability:
unstable
==============================*/
//suppose: 0<data[i]<100
//we should design the project function based on the data distribution
void bucket_sort(std::vector<int> &a)
{
std::vector<std::vector<int>> bucket;
bucket.resize(10);
std::vector<int>::iterator it=a.begin();
while(it!=a.end())
{
int idx=*it/10;
bucket[idx].push_back(*it);
it++;
}
std::vector<std::vector<int>>::iterator it1=bucket.begin();
while(it1!=bucket.end())
{
simple_sort(*it1);
it1++;
}
it=a.begin();
it1=bucket.begin();
while(it!=a.end() && it1!=bucket.end())
{
std::vector<int>::iterator tmp_it=(*it1).begin();
while(tmp_it!=(*it1).end())
{
*it=*tmp_it;
tmp_it++;
it++;
}
it1++;
}
}

``````