Comments 29
Прямо в стандарте ECMAScript
22.1.3.27 Array.prototype.sort ( comparefn )
The elements of this array are sorted. The sort must be stable (that is, elements that compare equal must remain in their original order).
А в стандартах других языков… ну, например, в C++ есть функция std::stable_sort.
return 0; использовать return a.localeCompare(b.name); и не полагаться на порядок?
let array = [
{name: "item 1", price: 100},
{name: "item 2", price: 100},
{name: "item 10", price: 100},
{name: "item 20", price: 100},
]попробуйте посравнивать строки в такой ситуации, например
Предлагаю следующую статью: почему перемешивание с помощью сортировки по Math.random — плохая идея.
Коварство в том, что обычно нативные реализации сортировки для маленьких массивов (в хроме — менее 10 элементов) используют не q-sort, а какую-то другую, стабильную сортировку. И если об этом не знать, то можно забыть проверить алгоритм на массиве покрупнее. Статья-предостережение, скажем так.
Интересно, почему в V8 запилили TimSort, а не BlockSort? У последнего space complexity O(1), в отличии от.
TimSort работает за линию по времени в случае уже отсортированного массива. Наверняка авторы V8 собирали статистику или свой код попрофилировали и выяснили, что избыточная пересортировка случается достаточно часто.
Если верить вики, TimSort чаще сортирует за время O(n), чем BlockSort.
https://en.wikipedia.org/wiki/Block_sort#Disadvantages :
Block sort does not exploit sorted ranges of data on as fine a level as some other algorithms, such as Timsort.
Статья действительно интересная, но мне кажется старый добрый мастер просто добавил бы сортировку по названию. А ещё лучше по индексу в массиве, если есть разумный способ его использования.
Нет, просто акцент у статьи немножко смещён.
Нестабильная сортировка — это разновидность случайной перестановки (не очень случайной, конечно же).
Тем более, что квиксорт специально рандомизируют, чтобы он не выродился в квадратичный пузырёк на упорядоченном наборе (а у нас набор упорядоченный, все элементы — "первые").
Как именно аукнется рандомизация в программе — возможны варианты.
Первое, что приходит в голову — это при сериализации получаются разные последовательности. То есть, умом-то мы понимаем, что в двух файлах одно и то же лежит, а побайтово — нет, кажется, разное.
(Этим грешило, в частности, MFC — контейнер CMap).
Или может вылезти какой-нибудь гейзенбаг, — который воспроизводится раз в 100500 запусков, при удачном стечении обстоятельств. (Баг всю жизнь есть, но рандомизация его прячет от нас).
Программисту может показаться, что порядок элементов в сортированном массиве или в ассоциативном контейнере ему не важен. А потом хоба — и оказалось, что важен.
Вот поэтому хэш-таблицы — страшная вещь.
И вот поэтому в третьем питоне, наконец-то, объявили, что хватит трепать людям нервы, пусть dict будет стабильным контейнером (OrderedDict из второго питона). Это по-прежнему хэш-таблица, но перечисление элементов — в исходном порядке, а не в том, как оно во внутренней табличке быстрого доступа сложилось.
И, думаю, поэтому же в стандарте экмаскрипта потребовали стабильность от сортировки.
Нужно понимать, что за стабильность надо платить дополнительную цену.
Это не просто "давайте в квиксорте будем сперва проверять вырожденные случаи — упорядоченного массива или массива эквивалентых элементов, чтобы за линейное время ничего не делать".
- Написать код, придумав свои спецификации ECMAScript
- Поудивляться, что есть баги, вставить картинку «магия»
- Найти решение, перейдя на более новую версию nodejs
- Узнать про спецификацию и про реализации в разных рантаймах и разных их версий
А по теме статьи: вам не нужна была своя сортировка, вам лишь надо было сделать так, чтобы компаратор не возвращал 0. Например сравнивая исходные индексы в массиве.
Но да, в некоторых случаях своя сортировка на js может быть быстрее.
- Подтяните фундаментальные знания об алгоритмах вообще и сортировках в частности, чтобы не заниматься археологией в поисках причины странного поведения.
Нестабильная сортировка в JavaScript