Стабильные алгоритмы сортировки в JavaScript

При сортировке данных сохранение исходного порядка равных элементов имеет решающее значение для стабильных алгоритмов сортировки. В этом контексте мы стремимся отсортировать массив объектов с определенным ключом в заданном порядке, сохраняя при этом согласованность порядка элементов.

Техника стабильной сортировки

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

Реализация в JavaScript

const sortBy = (arr, key, order) => {
  // Capture element positions
  const positions = arr.map((item, i) => {
    return { item, position: i };
  });

  // Perform sorting
  positions.sort((a, b) => {
    let cmp = a.item[key].localeCompare(b.item[key]);
    if (cmp === 0) {
      // Tiebreaker: sort by position
      cmp = a.position - b.position;
    }
    if (order === "desc") {
      return cmp * -1;
    } else {
      return cmp;
    }
  });

  // Return sorted objects
  return positions.map(position => position.item);
};

Пример использования

const data = [
  { name: "Alice", age: 25 },
  { name: "Bob", age: 30 },
  { name: "Eve", age: 25 },
];

const sortedAscending = sortBy(data, "age", "asc");
console.log(sortedAscending); // [{ name: "Alice", age: 25 }, { name: "Eve", age: 25 }, { name: "Bob", age: 30 }]

const sortedDescending = sortBy(data, "age", "desc");
console.log(sortedDescending); // [{ name: "Bob", age: 30 }, { name: "Eve", age: 25 }, { name: "Alice", age: 25 }]

Этот метод обеспечивает стабильную сортировку в JavaScript, сохраняя исходный порядок элементов с одинаковыми значениями.