Chương trình triển khai Bucket Sort trong JavaScript

Chương trình triển khai Bucket Sort trong JavaScript

Bucket Sort hoạt động bằng cách chia mảng kích thước n thành k bucket (thùng) chứa các phạm vi giá trị phần tử cụ thể.

Sau đó, các bucket này được sắp xếp bằng một thuật toán sắp xếp có thể chọn dựa trên kích thước đầu vào mong đợi.

Chúng ta có thể mô tả thuật toán này như sau:

Thuật toán:

Tạo hàm bucketSort ban đầu
Tạo biến cho i, min, max, và kích thước bucket
Tìm giá trị min và max
Tạo số lượng bucket
Đẩy giá trị vào bucket đúng
Sắp xếp các bucket

Ví dụ

Mã thực hiện như sau:

const arr = [32, 6, 34, 4, 78, 1, 6767, 4, 65, 34, 879, 7];
const bucketSort = arr => {
  if (arr.length === 0) {
    return arr;
  }
  let i,
  minValue = arr[0],
  maxValue = arr[0],
  bucketSize = 5;
  arr.forEach(function (currentVal) {
    if (currentVal < minValue) {
      minValue = currentVal;
    } else if (currentVal > maxValue) {
      maxValue = currentVal;
    }
  })
  let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let allBuckets = new Array(bucketCount);
  for (i = 0; i < allBuckets.length; i++) {
    allBuckets[i] = [];
  }
  arr.forEach(function (currentVal) {
    allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);
  });
  arr.length = 0;
  allBuckets.forEach(function(bucket) {
    insertion(bucket);
    bucket.forEach(function (element) {
      arr.push(element)
    });
  });
  return arr;
}
const insertion = arr => {
  let length = arr.length;
  let i, j;
  for(i = 1; i < length; i++) {
    let temp = arr[i];
    for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
      arr[j+1] = arr[j];
    }
    arr[j+1] = temp;
  }
  return arr;
};
console.log(bucketSort(arr));

Đầu ra

Kết quả trong console:

[ 
  1, 4, 4, 6, 
  7, 32, 34, 34, 
  65, 78, 879, 6767 ]