0
\$\begingroup\$

I was asked to implement bucket sort recently from my friend.

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem. Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.

How do we sort the numbers efficiently? I would like to ask for feedback for my solution. I also performed some diagram and benchmark it against quicksort. I appreciate any feedback.

function bucketsort(arr, range_min, range_max) {
  if (arr.length <= 1) {
    return arr;
  }
  if (arr.length < 20) {
    return arr.sort();
  }

  let result = [];
  let numberOfBuckets = Math.ceil(Math.sqrt(arr.length));

  for (let i = 0; i < numberOfBuckets; i++) {
    result.push([]);
  }

  let bucketRange = (range_max - range_min) / numberOfBuckets;

  for (let i = 0; i < arr.length; i++) {

    let bucketIndex = Math.floor((arr[i] - range_min) / bucketRange);

    result[bucketIndex].push(arr[i]);
  }

  let finalResult = []
  for (let i = 0; i < result.length; i++) {
    finalResult = finalResult.concat(bucketsort(result[i], i * bucketRange + range_min, (i+1) * bucketRange + range_min));
  }

  return finalResult;
}


// console.log(bucketsort([0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434, 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434], 0.0, 1.0));



// console.log(bucketsort([1,2,3,4,5,6,7,8,9,10,11,12,13,14], 0, 15));


// bucketRange = 0.33333
//
//     0.0        0.333       0.666       1.0
//     [ [       ],  [       ],  [       ]]





// calling bucketsort on large arrays compared to quicksort

let test = [];

for (let i = 0; i < 100000; i++) {
  test.push(Math.random());
}



function quicksort(arr) {
  return arr.sort((a, b) => {
    return a - b;
  });
}


console.time("quicksort: ");
quicksort(test);
console.timeEnd("quicksort: ");


console.time("bucketsort: ");
bucketsort(test, 0.0, 1.0);
console.timeEnd("bucketsort: ");

Array.sort
\$\endgroup\$
  • \$\begingroup\$ What is the useless Array.sort doing at the end? \$\endgroup\$ – 200_success Feb 6 at 18:49
  • \$\begingroup\$ just for testing the output is the same \$\endgroup\$ – NinjaG Feb 6 at 20:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.