Since many algorithm problems in LeetCode involve some basic data structures, in order to better understand the animation of some complex problems updated later, a new series —– “Illustrated Data Structures” is launched, mainly using animation to describe common data structures and algorithms. This series includes ten kinds, heap, queue, tree, and search set, graph and so on about dozens of articles.

Bucket sort

Bucket sort is a counting sort algorithm (see the previous section for counting sort) that works by sorting the data into a limited number of buckets and then sorting each Bucket separately (it is possible to use another sort algorithm or to continue sorting using Bucket sort recursively).

Algorithm steps

  1. Set a fixed number of empty buckets.

  2. Put the data into the corresponding bucket.

  3. Sort the data in each bucket that is not empty.

  4. Concatenate the data in the bucket that is not empty to obtain the result.

Algorithm demo

Animated demo GIF is a bit slow to load, please wait a moment

Sort animation process explanation

  1. First, set a fixed number of empty buckets. For demonstration purposes, set the number of empty buckets to 5

  2. Iterate through the entire array to find a maximum value of 56, a minimum value of 2, and a range of (56-2 + 1) / 5 = 11 for each bucket

  3. Iterate through the entire array again, following the formula floor((numeral — minimum) / 11) to place the number in the appropriate bucket

  4. For example, the number 7 is substituted into the formula floor((7-2) / 11) = 0 and placed in bucket 0

  5. The number 12 is substituted into the formula floor((12 — 2) / 11) = 0 and placed in bucket 0

  6. The number 56 is substituted into the formula floor((56 — 2) / 11) = 4 and placed in bucket 4

  7. When inserting data into the bucket with the same index for the second time, determine the size of the existing number and the newly inserted number in the bucket in ascending order from left to right (you can use the insert sort described above)

  8. For example, when the number 19 is inserted, bucket 1 already has the number 23, so use insertion sort to rank 19 before 23

  9. After the entire sequence is traversed, merge the non-empty buckets, merging 0,1,2,3,4 buckets from left to right.

  10. This completes bucket sorting

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post a variety of programming language reference code, code all from the Internet.

C++ code implementation

Java code implementation

JavaScript code implementation