Стабильная `Array.prototype.sort`
Допустим, у вас есть массив собак, где каждая собака имеет имя и рейтинг. (Если это кажется странным примером, знайте, что существует аккаунт в Twitter, который специализируется именно на этом… Не спрашивайте!)
// Обратите внимание, что массив предварительно отсортирован по алфавиту по `name`.
const doggos = [
{ name: 'Abby', rating: 12 },
{ name: 'Bandit', rating: 13 },
{ name: 'Choco', rating: 14 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
{ name: 'Falco', rating: 13 },
{ name: 'Ghost', rating: 14 },
];
// Сортируем собак по рейтингу в порядке убывания.
// (Это обновляет `doggos` на месте.)
doggos.sort((a, b) => b.rating - a.rating);
Массив предварительно отсортирован по алфавиту по имени. Чтобы сортировать по рейтингу (чтобы сначала получить собак с самым высоким рейтингом), мы используем Array#sort
, передавая пользовательский колбэк, который сравнивает рейтинги. Вот результат, который вы, вероятно, ожидаете:
[
{ name: 'Choco', rating: 14 },
{ name: 'Ghost', rating: 14 },
{ name: 'Bandit', rating: 13 },
{ name: 'Falco', rating: 13 },
{ name: 'Abby', rating: 12 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
]
Собаки сортируются по рейтингу, но внутри каждого рейтинга они все еще отсортированы по алфавиту по имени. Например, Choco и Ghost имеют одинаковый рейтинг 14, но Choco появляется перед Ghost в результате сортировки, потому что это тот порядок, который они имели в исходном массиве.
Однако, чтобы получить этот результат, движок JavaScript не может просто использовать любой алгоритм сортировки — он должен быть так называемой «стабильной сортировкой». Долгое время спецификация JavaScript не требовала стабильности сортировки для Array#sort
и оставляла это на усмотрение реализации. И поскольку это поведение не было определено, вы также могли получить этот результат, где Ghost неожиданно появляется перед Choco:
[
{ name: 'Ghost', rating: 14 }, // 😢
{ name: 'Choco', rating: 14 }, // 😢
{ name: 'Bandit', rating: 13 },
{ name: 'Falco', rating: 13 },
{ name: 'Abby', rating: 12 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
]
Другими словами, разработчики JavaScript не могли полагаться на стабильность сортировки. На практике ситуация была еще более раздражающей, так как некоторые движки JavaScript использовали стабильную сортировку для коротких массивов и нестабильную сортировку для больших массивов. Это было действительно сбивающим с толку, так как разработчики тестировали свой код, видели стабильный результат, но внезапно получали нестабильный результат в продакшене, когда массив немного увеличивался.
Но есть хорошие новости. Мы предложили изменение в спецификации, которое делает Array#sort
стабильным, и оно было принято. Все основные движки JavaScript теперь реализуют стабильную Array#sort
. Это просто еще одна вещь, о которой не нужно беспокоиться как разработчику JavaScript. Отлично!
(О, и мы сделали то же самое для TypedArray
: теперь эта сортировка тоже стабильная.)
Примечание: Хотя стабильность теперь требуется в соответствии со спецификацией, движки JavaScript по-прежнему могут использовать любой алгоритм сортировки, который они предпочитают. V8 использует Timsort, например. Спецификация не предписывает какой-либо конкретный алгоритм сортировки.