JavaScriptでバケットソートを実装するプログラム

バケットソートは、サイズnの配列を特定の範囲の要素値を保持するk個のバケットに分割することで機能します。

次に、これらのバケットは、予想される入力サイズに基づいて選択できる並べ替えアルゴリズムを使用して並べ替えられます。

このアルゴリズムは次のように説明できます-

アルゴリズム：

Create the initial bucketSort function
Create variables for i, min, max, and bucket size
Find min and max value
Create amount of buckets
Push values to correct buckets
Sort buckets

例

このためのコードは-

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));

出力

コンソールの出力-

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