preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Bucket sort (also known as box sort) is also a distributed sorting algorithm, which sorts elements into buckets (smaller arrays) and sorts each bucket using a simple sorting algorithm, such as insertion sort (a nice algorithm for sorting small arrays). It then merges all the buckets into a result array.

Train of thought

For example arrays [3, 8, 6, 1, 5, 7, 9, 2, 4]

  • Divide: Create buckets and distribute elements into different buckets. An important step in bucket sorting is to count the number of elements that need to be distributed in each bucket
  • Sorting: Sort the elements of the sorted bucket by # insertion
  • And: Finally, merge the data of each bucket to complete sorting

See the following code explanation

implementation

function bucketSort(array, bucketSize = 5) {
  if (array.length <= 1) return array;
  var buckets = createBuckets(array, bucketSize) // Create buckets and distribute elements into different buckets
  return sortBuckets(buckets);
}

// Create buckets and distribute elements into different buckets
function createBuckets(array, bucketSize) { // bucketSize specifies the capacity of each bucket
  var maxValue = Math.max(... array);// Select * from ES6
  var minValue = Math.min(... array);// Select * from ES6

  var bucketCount = Math.ceil((maxValue - minValue) / bucketSize) // The first important step in bucket sorting is to calculate the number of elements that need to be distributed in each bucket
  var buckets = [];
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = []; // Initialize each bucket to empty
  }
  for (var i = 0; i < array.length; i++) {
    var bucketIndex = Math.floor((array[i] - minValue) / bucketSize); // Calculate which bucket to put the element in
    buckets[bucketIndex].push(array[i]); // Store elements into buckets
  }
  return buckets
}
// Sort each bucket
function sortBuckets(buckets) {
  var sortedArray = [];
  for (let i = 0; i < buckets.length; i++) {
    if(buckets[i] ! =null) {
      sortedArray.push(...insertionSort2(buckets[i]));
    }
  }
  return sortedArray;
}

// Insert sort
function insertionSort2(array) {
  if (array.length <= 1) return array; // If the array length is 1, return it directly
  var sum = 0 // Count the number of loops
  for (var i = 1; i < array.length; i++) {
    var j = i; // Take index 1 as an example
    var temp = array[j]; // Store a value to compare and start comparing forward
    / / 1. If the temp < arr [1], the arr [1] ward (if arr = arr [j] [1]).
    // 2. If temp < ARR [J-2], arR [J-2] = arr[j-2];
    //   若temp>arr[j-2]，则arr[j-1] = temp
    while (j > 0 && array[j - 1] > temp) {
      sum++
      array[j] = array[j - 1]; // This can be seen as moving j-1 one bit back
      j--;
    }
    array[j] = temp;
  }
  console.log('sum: ', sum); / / 6
  return array;
}

var arr = [3.8.6.1.5.7.9.2.4];
console.log(bucketSort(arr));
Copy the code

To optimize the

No other optimization ideas, welcome to comment

The complexity of the

Sorting algorithm Average time complexity The best situation The worst Spatial complexity The sorting way The stability of
Bucket sort O(n+k) O(n+k) It depends O(n+k) Out-place stable
  • Time complexity

Data after barrels of division, some of the bucket data very much, some of the very few, is very uneven, and data within the bucket sort time complexity, it is not a constant level, level is linear O (n), can be simple to understand: the scope of the bucket size is specified, it does not change with data size, if the data is relatively evenly distributed, so the number of barrels is the core factors.

  • Spatial complexity

  1. Bucket sort is distributed sort, suitable for processing large amounts of data. You need extra space. External sort. The stability of bucket sorting depends on the selection of the sorting algorithm in the second step. Data size n, divided into K buckets, total space complexity O(n + K)

  2. Bucket sorting has very strict requirements on sorted data, and applies to scenarios where the data distribution is relatively uniform or the data span is not large. If the data span is very large, the space consumption will be very large. If the data is divided into a bucket, bucket sorting will degenerate to O(nlogn) sorting algorithm, so bucket sorting is rarely used.

other

# front-end algorithm learning – algorithm complexity # front-end required algorithm (a) : bubble sort # front-end required algorithm (B) : select sort # front-end required algorithm (C) : Insert sort # front-end required algorithm (C) : merge sort # front-end required algorithm (C) : quick sort # front-end required algorithm (C) : Hill sort # Front-end will algorithm (7) : counting sort

The last

Dregs a, welcome all great god many correction, not praise, just supervision correction

reference

# Write the algorithm and remember it: bucket sort