Реализация сортировки "корзинка" на JavaScript

Введение

В этом лабе мы будем изучать алгоритм сортировки "корзинка" (bucket sort) на JavaScript. Алгоритм сортировки "корзинка" работает путём распределения элементов массива по нескольким "корзинам". Затем каждая "корзина" сортируется отдельно, либо с использованием другого алгоритма сортировки, либо путём рекурсивного применения алгоритма сортировки "корзинка". В этом лабе вам будет предоставлено возможность реализовать этот алгоритм и получить более глубокое понимание того, как он работает.

Skills Graph

Алгоритм сортировки "корзинка"

Чтобы использовать алгоритм сортировки "корзинка" и отсортировать массив чисел, следуйте шагам:

1. Откройте Терминал/SSH и введите node, чтобы начать практиковать программирование.
2. Найдите минимальное и максимальное значения заданного массива с использованием Math.min(), Math.max() и оператора расширения (...).
3. Создайте соответствующее количество "корзин" (пустых массивов) с использованием Array.from() и Math.floor().
4. Заполните каждую "корзину" соответствующими элементами из массива с использованием Array.prototype.forEach().
5. Отсортируйте каждую "корзину" и добавьте её в результат с использованием Array.prototype.reduce(), оператора расширения (...) и Array.prototype.sort().

Вот пример реализации алгоритма сортировки "корзинка" на JavaScript:

const bucketSort = (arr, size = 5) => {
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const buckets = Array.from(
    { length: Math.floor((max - min) / size) + 1 },
    () => []
  );
  arr.forEach((val) => {
    buckets[Math.floor((val - min) / size)].push(val);
  });
  return buckets.reduce((acc, b) => [...acc, ...b.sort((a, b) => a - b)], []);
};

Чтобы протестировать алгоритм, запустите следующий код:

bucketSort([6, 3, 4, 1]); // [1, 3, 4, 6]

Резюме

Поздравляем! Вы завершили лабу по сортировке "корзинка". Вы можете практиковаться в других лабах в LabEx, чтобы улучшить свои навыки.