“This is the 21st day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Bucket sort

introduce

Bucket sort is also an advanced version of counting sort algorithm.

It is divided into a specific number of buckets. After obtaining the maximum and minimum values in the buckets to be sorted, a range of distribution is carried out and the buckets are successively put into the buckets.

Finally, any 7 comparison sorting algorithms are sorted in each bucket, so as to reduce the number of comparisons.

Finally, the data in each bucket is sequentially spliced, which is the final sorting result.

• Dynamic graph demonstration

  

Break down

• Operating points barrel

  Given a constant value of how many buckets to divide data items into, bucketCount

• Get the maximum and minimum values

  This is done by setting minValue and maxValue.

      const maxValue = Math.max(... arr)const minValue = Math.min(... arr)Copy the code

• Figure out the range of each bucket

  The maximum value and minimum value are divided by bucketCount to obtain the range

    bucketSize = Math.floor((maxValue - minValue + 1) / bucketCount)
  Copy the code

• Create each bucket and distribute data to the bucket

  Through a loop, we create each bucket, and then we loop through the array ARR, evaluate the current value in that range, and then distribute it.

      Math.floor((arr[i] - minValue) / bucketCount)
  Copy the code

• Bucket sorting alone

  Each bucket is sorted separately, using one of the seven comparison sorts. I’m just going to use the code, and for the sake of convenience, I’m just going to use sort of the array.

      bucket[i].sort()
  Copy the code

• merge

  Finally, merge each bucket, extract sorted results from each bucket and push them into the result array. We’re going to get the bucket sort that we want in the end

The complete code

    /** * Bucket sorting, bucketCount is divided into buckets *@param {array} arr 
     * @param {number} bucketCount 
     * @returns * /
    const bucketSort = (arr, bucketCount) = > {
      const result = []
      
      // Find the maximum and minimum values in preparation for assigning the size to each bucket
      const maxValue = Math.max(... arr)const minValue = Math.min(... arr)// Find the size of each bucket
      bucketSize = Math.floor((maxValue - minValue + 1) / bucketCount)
      bucket = new Array(bucketCount)
      for (let i = 0; i < bucketCount; i++) {
        bucket[i] = []
      }
      // Add data to the bucket
      for (let i = 0; i < arr.length; i++) {
        bucket[Math.floor((arr[i] - minValue) / bucketCount)].push(arr[i])
      }
      // Sort each bucket individually and place it in the result array
      for (let i = 0; i < bucketCount; i++) {
        bucket[i].sort()
        for (let j = 0; j < bucket[i].length; j++) {
          result.push(bucket[i][j])
        }
      }
      return result
    }
    / / test
    arr = [5.4.3.2.1.8.6.4.7.6]
    console.log(bucketSort(arr, 3))
Copy the code

conclusion

Bucket sort is non-comparison sort and also a stable sort.

Is an advanced version of counting sort, and bucket sort also uses other sort related knowledge.