Example of a method for implementing bucket sorting in C language

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++;
  }
}

PS: here is another demonstration tool about sorting for your reference:

Animation demo insert/select/bubble/merge/hill/quick sort algorithm process tool:
http://tools.ofstack.com/aideddesign/paixu_ys

I hope this article has been helpful to you in the programming of C language.