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

Введение

В этом практическом занятии мы изучим реализацию алгоритма сортировки вставками на JavaScript. Мы узнаем, как сортировать массив чисел с использованием этого алгоритма, и поймем логику, лежащую в основе его. В конце этого практического занятия вы сможете использовать алгоритм сортировки вставками для эффективной сортировки массивов в своих проектах на JavaScript.

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

Для практики программирования откройте Терминал/SSH и введите node. Этот алгоритм сортирует массив чисел с использованием метода сортировки вставками. Следуйте шагам, чтобы реализовать этот алгоритм:

1. Используйте Array.prototype.reduce(), чтобы пройти по всем элементам в заданном массиве.
2. Если длина накопителя равна 0, добавьте текущий элемент в него.
3. Используйте Array.prototype.some(), чтобы пройти по результатам в накопителе, пока не будет найдена правильная позиция.
4. Используйте Array.prototype.splice(), чтобы вставить текущий элемент в накопитель.

Вот код для реализации сортировки вставками на JavaScript:

const insertionSort = (arr) =>
  arr.reduce((acc, x) => {
    if (!acc.length) return [x];
    acc.some((y, j) => {
      if (x <= y) {
        acc.splice(j, 0, x);
        return true;
      }
      if (x > y && j === acc.length - 1) {
        acc.splice(j + 1, 0, x);
        return true;
      }
      return false;
    });
    return acc;
  }, []);

Вы можете протестировать алгоритм с помощью следующего кода:

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

Резюме

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