What is bucket sort?

Bucket sort is an updated version of count sort, which is not available in some sort scenarios (values are out of range or are not integers). Sort the data into a finite number of buckets and sort each bucket separately (it is possible to use another sort algorithm or continue to use bucket sort recursively)

Algorithm description

Set n number of empty buckets and determine the range of each bucket;

Iterate through the input data and put the data one by one into the corresponding bucket;

Sort each bucket that can be sorted (the number of buckets in the bucket is greater than 1).

Stitch the sorted buckets together

chestnuts

Each bucket represents an interval range that can hold one or more elements.

The first step in bucket sorting is to create the buckets and determine the range of each bucket

<img src=”https://noxussj.top:3000/29/1.png”></img>

And at this point people say, how do you know how many buckets to build? What is the range of each bucket?

How many buckets do you build, how do you define the interval of the buckets, there are a lot of different ways, depending on the actual situation

To give just one example, the number of buckets created is equal to the number of elements in the original sequence, except that the last bucket contains only the maximum value of the sequence, and the intervals of the preceding buckets are proportional

Interval span (average) = (maximum – minimum)/(number of buckets – 1)

The second step is to traverse the original sequence, matching the elements and placing them in each bucket

<img src=”https://noxussj.top:3000/29/2.png”></img>

Third, the elements inside each bucket are sorted separately (obviously, only the first bucket needs to be sorted)

<img src=”https://noxussj.top:3000/29/3.png”></img>

The final step is to iterate through all the buckets and print out all the elements

0.5, 0.84, 2.18, 3.25, 4.5

Comics: What is bucket sort?

additional

  • This article is published through multiple platforms of “We Media” and will not be maintained after publication. If you have any objection to the content, you can discuss it in the GitHub below
  • The ongoing maintenance / 500 + face questions before update/notes 】 https://github.com/noxussj/In…
  • [3D city modeling using three. JS (Zhuhai City)] https://3d.noxussj.top/