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

JavaScriptJavaScriptBeginner
Практиковаться сейчас

This tutorial is from open-source community. Access the source code

💡 Этот учебник переведен с английского с помощью ИИ. Чтобы просмотреть оригинал, вы можете перейти на английский оригинал

Введение

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


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("JavaScript")) -.-> javascript/BasicConceptsGroup(["Basic Concepts"]) javascript(("JavaScript")) -.-> javascript/AdvancedConceptsGroup(["Advanced Concepts"]) javascript/BasicConceptsGroup -.-> javascript/variables("Variables") javascript/BasicConceptsGroup -.-> javascript/data_types("Data Types") javascript/BasicConceptsGroup -.-> javascript/arith_ops("Arithmetic Operators") javascript/BasicConceptsGroup -.-> javascript/comp_ops("Comparison Operators") javascript/AdvancedConceptsGroup -.-> javascript/higher_funcs("Higher-Order Functions") javascript/AdvancedConceptsGroup -.-> javascript/spread_rest("Spread and Rest Operators") subgraph Lab Skills javascript/variables -.-> lab-28181{{"Реализация сортировки #quot;корзинка#quot; на JavaScript"}} javascript/data_types -.-> lab-28181{{"Реализация сортировки #quot;корзинка#quot; на JavaScript"}} javascript/arith_ops -.-> lab-28181{{"Реализация сортировки #quot;корзинка#quot; на JavaScript"}} javascript/comp_ops -.-> lab-28181{{"Реализация сортировки #quot;корзинка#quot; на JavaScript"}} javascript/higher_funcs -.-> lab-28181{{"Реализация сортировки #quot;корзинка#quot; на JavaScript"}} javascript/spread_rest -.-> lab-28181{{"Реализация сортировки #quot;корзинка#quot; на JavaScript"}} end

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

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

  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, чтобы улучшить свои навыки.