Шаг 1

Некоторые веб-приложения выводят уже сортированный набор данных пользователю, а затем, дозапрашивая данные с сервера, добавляют их в этот набор и сортируют заново. Но ведь гораздо проще и эффективнее, имея небольшой массив и небольшой набор добавляемых данных, просто поддерживать наш массив отсортированным! Самый простой из примеров, где это может использоваться — инвестиционное приложение, которое сразу же показывает сегодняшние цены на популярные акции, а затем подгружает остальные. Как уже было сказано в прошлой статье, сортировка вставкой — одна из немногих, которая может с небольшой сложностью поддержать любой наш список сортированным. Давайте напишем функцию sortPush, с помощью которой можно будет добавить новый элемент в уже отсортированный массив из цен акций.

import {log} from "./logger";

function sortPush(array, element) {
  return array;
}

// Список из заранее загруженных данных
const data = [
  {
    ticker: 'WISH',
    price: 5.14
  },
  {
    ticker: 'SPCE',
    price: 20.10
  },
  {
    ticker: 'AAPL',
    price: 151.86
  },
  {
    ticker: 'QCOM',
    price: 155.98,
  },
  {
    ticker: 'ABNB',
    price: 178.06,
  }
];

const loaded = {
  ticker: 'BABA',
  price: 166.99
}

log(sortPush(data, loaded)); // Добавит новый элемент предпоследним в наш список

Шаг 2

Несмотря на то, что мы рассматривали сортировку вставкой только в связном списке, алгоритм вставки в массив почти не меняется: нам также нужно сначала найти место, где должен встать новый элемент, найдя первый элемент больше него.

import {log} from "./logger";

function sortPush(array, element) {
  // Сначала предположим, что элемент пойдет прямо в начало массива
  let pointOfInsertion = 0;

  // Пока не встретим элемент больше вставляемого или конец массива...
  while (pointOfInsertion < array.length && element.price > array[pointOfInsertion].price) {
    // ... двигаем указатель на место вставки
    pointOfInsertion++;
  }

  return array;
}

// Список из заранее загруженных данных
const data = [
  {
    ticker: 'WISH',
    price: 5.14
  },
  {
    ticker: 'SPCE',
    price: 20.10
  },
  {
    ticker: 'AAPL',
    price: 151.86
  },
  {
    ticker: 'QCOM',
    price: 155.98,
  },
  {
    ticker: 'ABNB',
    price: 178.06,
  }
];

const loaded = {
  ticker: 'BABA',
  price: 166.99
}

log(sortPush(data, loaded)); // Добавит новый элемент предпоследним в наш список

Шаг 3

А вместо обновления связей, как мы сделали бы в связном списке, разделим наш массив на части до и после вставляемого элемента и положим его между ними.

import {log} from "./logger";

function sortPush(array, element) {
  // Сначала предположим, что элемент пойдет прямо в начало массива
  let pointOfInsertion = 0;

  // Пока не встретим элемент больше вставляемого или конец массива...
  while (pointOfInsertion < array.length && element.price > array[pointOfInsertion].price) {
    // ... двигаем указатель на место вставки
    pointOfInsertion++;
  }

  return pointOfInsertion === 0
    ? [element, ...array]
    : [...array.slice(0, pointOfInsertion), element, ...array.slice(pointOfInsertion)];
}

// Список из заранее загруженных данных
const data = [
  {
    ticker: 'WISH',
    price: 5.14
  },
  {
    ticker: 'SPCE',
    price: 20.10
  },
  {
    ticker: 'AAPL',
    price: 151.86
  },
  {
    ticker: 'QCOM',
    price: 155.98,
  },
  {
    ticker: 'ABNB',
    price: 178.06,
  }
];

const loaded = {
  ticker: 'BABA',
  price: 166.99
}

log(sortPush(data, loaded)); // Добавит новый элемент предпоследним в наш список

File logger

  const results = document.getElementById('results')

export function log(stocks) {
  for (const {ticker, price} of stocks) {
    const result = document.createElement('li');

    result.innerHTML = `${ticker}: ${price}$`;

    results.appendChild(result);
  }
}