“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Algorithm thought

Bucket sort divides multiple ranges of the same scope (buckets), the elements in each range are sorted, and then merged into a new range. Bucket sort is an extended version of counting sort (see this article for more on counting sort). Counting sort can be thought of as one element per bucket, and each bucket needs to hold a certain range of elements, eventually creating a new space for the results.

Graphic algorithm

  1. Determine the number of buckets and the range of each bucket,
  2. Place the elements of the original array in their respective buckets
  3. Each bucket is sorted separately, and we can use insert sort here

4. Output the elements of the bucket array to the new storage space

Code implementation

  • Let’s look at the implementation of counting sort
function countSort(arr) {
  let max = -Infinity, 
    min = Infinity
  for (let v of arr) {
    max = Math.max(max, v)
    min = Math.min(min, v)
  }
  const count = new Array(max - min + 1).fill(0) // Array length Max - min, min becomes subscript 0,
  // If the difference between the maximum and minimum values is large, there is still a waste of space
  for (let v of arr) {
    count[v - min]++ // Subtract the minimum
  }
  const res = [] 
  for (let i = 0; i < count.length; i++) {
    let tmp = count[i]
    while (tmp--) {
      res.push(i + min) // Add back here}}return res
}
const arr = [-101.109.107.103.108.102.103.110.107.103]
console.log(countSort(arr)) //[-101, 102, 103, 103, 103, 107, 107, 108, 109, 110]
Copy the code
  • Bucket sort divides buckets on the basis of counting sort to reduce the waste of space
function bucketSort(arr) {
  // Find the maximum and minimum values
  let max = -Infinity,
    min = Infinity
  for (let v of arr) {
    max = Math.max(max, v)
    min = Math.min(min, v)
  }
  // Generate an array of buckets
  const bucketNum = Math.floor((max - min) / arr.length) + 1 / / number of barrels
  let bucketArr = new Array(bucketNum).fill(null)
  bucketArr = bucketArr.map(_= > [])
  // Each element goes into a bucket
  for (let v of arr) {
    let index = Math.floor((v - min) / arr.length)
    bucketArr[index].push(v)
  }
  // Result array
  const res = []
  for (let item of bucketArr) {
    // Other sorts can be done
    item.sort((a, b) = > a - b)
    / / output
    for (let v of item) {
      res.push(v)
    }
  }
  return res
}

const arr = [14.28.10.24.35.50.39.47]
console.log(bucketSort(arr)) // [10, 14, 24, 28, 35, 39, 47, 50]
Copy the code

— end —