Ну, тут не памятью жертвуем, хотя она может дойти до O(log N)

Т.е. если мало элементов, то из-за константного деления на 4, выгоднее казалось бы ненужный алгоритм Если эелментов много, то логично использовать тяжелый алгоритм, но он будет в 2 раза тяжелее в среднем, НО ГАРАНТИРОВАННО. Если среднее число элементов, то просто квик сорт

это я про heap sort vs merge sort, и вообще в принципе

нормальная история. смотрю весело тебе, будем называть тебя мистер квик сорт 😉

Если тебе интересны всякие такие плюсовые штуки применительно к спортивному программированию, советую вот эту книгу https://cses.fi/book/book.pdf , там всякие алгоритмы и сразу с фишками для реализации

Для начала сложности сортировок (критерий O(1) память, поэтому merge не подходит): 1) insertion sort: avg(N^2 / 4) worst(N^2 / 2) 2) quick sort: avg(N log N) worst(N^2) 3) heap sort: avg(2 * N logN) worst(2 * N logN) ОЧЕНЬ ВАЖНЫ константы на которые мы делим В общем стандартная сортировка в плюсах работает вроде так: Смотрим подмассива: if len < 8: insertion sort else if len > 1000: heap sort else: quick sort

Наблюдения: arr = [ ...arr.slice(0, j), arr[i], ...arr.slice(j, i), ...arr.slice(i + 1), ]; Очень дорогая операция, и никак не оптимизируется

а что это за сортировка?

а что это за сортировка?

необычно)

Наблюдения: arr = [ ...arr.slice(0, j), arr[i], ...arr.slice(j, i), ...arr.slice(i + 1), ]; Очень дорогая операция, и никак не оптимизируется

Охереть, JSPerrf использовал benchmark js который использовал lodash _.now() что является простой Date.now()

это, не помню просто такого в реализации insertion sort

Ну да, я думал не свапать каждый раз, а один раз сделать новый массив слайсами. По сути одно и тоже

при свапе не создается новые массивы, а при слайсах - да

ну insertionSort (если правильно реализован) быстрее работает на почти отсортированных данных, поэтому могло так произойти

https://www.toptal.com/developers/sorting-algorithms

тут надо смотреть правильно ли реализованы другие сортировки

тут надо смотреть правильно ли реализованы другие сортировки

Можешь ему писать претензии к Array.prototype.sort https://twitter.com/ryanmdahl 🤣

ну я хз как при рандомных значениях O(n log n) может быть медленнее O(n2)

ну я хз как при рандомных значениях O(n log n) может быть медленнее O(n2)

они могут отличаться от операционки, проца, браузера (интерпретатора точнее) и тд

главное какое значение Big O ну и ему подобные

Больше влияет оптимизация в JS, т.к. O у всех почти одинаковая

фишка в том, что на одной версии V8 (в ноде который) может быть быстрее одно, а на другой версии - другое) Там столько задротства в этом движке, что жесть

фишка в том, что на одной версии V8 (в ноде который) может быть быстрее одно, а на другой версии - другое) Там столько задротства в этом движке, что жесть

Почему же, кроме мажорных версий по типу 8 и 12?)))

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

Откуда у вас такие суждения?

Для начала сложности сортировок (критерий O(1) память, поэтому merge не подходит): 1) insertion sort: avg(N^2 / 4) worst(N^2 / 2) 2) quick sort: avg(N log N) worst(N^2) 3) heap sort: avg(2 * N logN) worst(2 * N logN) ОЧЕНЬ ВАЖНЫ константы на которые мы делим В общем стандартная сортировка в плюсах работает вроде так: Смотрим подмассива: if len < 8: insertion sort else if len > 1000: heap sort else: quick sort

Если ну очень хочется заморочится, но мб было бы полезно в репозитории помимо кода, собрать в readme интересные и важные заметки о сортировках. В читабельном формате (а не просто пару комментов к коду). Пример (все еще не идеальный, так как собрана только самая базовая инфа): https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort С описаниями вроде: - почему одни сортировки полезнее других - почему применяются O(Oˆ2) сортировки. Как в приведенном примере про различные константы. Мб с конкретными примерами, сравнения кол-ва элементарных операций при размере инпута. Пример этого можно найти здесь: Видео: https://www.youtube.com/watch?v=FJJTYQYB1JQ&ab_channel=CppCon Слайды (начиная с 13 страницы и это чуть к другому докладу): https://github.com/aTan-aka-Xellos/algorithms-projector/blob/master/info/Allegro%20Means%20Both%20Fast%20and%20Happy%20-%20Andrei%20Alexandrescu%20(2).pdf - почему QuickSort в худшем случае квадрат (постоянно забываю перепроверить и это редко кто объясняет) - влияние кеширования и branch-prediction на сортировки http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/ Ниже мб не самый удачный пример, так как для BS кол-во итераций маленькое и это не заметно, но тем ни менее: https://leetcode.com/problems/binary-search/discuss/884875/java-simplestshortest-bs-without-confusing-indexes Почти все BS используют 2 if внутри цикла, для сравнения с таргетом, хотя это можно вынести вне цикла. Почему то никто почти не использует этот паттерн. При том, что здесь еще и не нужно заморачиватся с запоминанием куда добавлять 1. - какие сортировки стабильные и в чем польза

@vitkarpov Заэпрувьте мне merge sortы, чтобы я тестировать производительность начала 😃

Мердж! 🚀

Привет! Рад присоединиться! :) Проект продвигается медленно но уверенно- пока только на youtube. Неделю назад отметил 5000 подписчиков.

А я вот сидел читал как раз твой блог - статью про HTTPS. Понял, что много не знал как это все работает за кулисами.

Привет! Рад присоединиться! :) Проект продвигается медленно но уверенно- пока только на youtube. Неделю назад отметил 5000 подписчиков.

Ясно. В онлайне выгоднее выходит?