Как пошагово работает сортировка .sort()?

Question

[Михаил Оловянников]

Запутался в сортировке .sort() не понимаю как она работает по шагам. Вот пример кода:

[1, -2, 15, 2, 0, 8].sort(function (a, b) {
    console.log(`${a - b}`);
    console.log(a + " <> " + b);
    return a - b;
});

Первое что я не понимаю - почему в переменную а в самом начале работы алгоритма идет -2 а в переменную b идет 1, мне кажется, что все должно работать наоборот. 1 должно быть в а и соответственно -2 в b:
Потом я не понимаю следующее: при первом сравнении результат -3, то есть -2 должно переместится влево за 1. Почему второе сравнение сравнивает 15 и -2? А потом вообще 2 и 1. Как этот алгоритм работает я что-то вообще не понимаю. Можете пошагово объяснить, как он в массиве меняет значения и почему это все так?

Answer 1

[mayton2019]

Поскольку вопрос тегирован алгоритмами - человек пытается ИХ изучать а не контракт array.sort.

В науке и технике... в качестве алгоритма сортировки любят использовать сортировку Хоара.
Она-же Quick Sort. Еще в переводной литературе ее называют Быстрая сортировка делением.

Еще я где-то читал (не помню где! блин) что ядро Linux иногда использует для своих нужд HeapSort.
Или сортировку Пирамидой. Или пирамидальную. Достаточно быстрая и не требующая дополнительной памяти
вообще. По месту сортирует.

Более полное демо по алгоритмам с визуализацией здесь

https://www.youtube.com/watch?v=kPRA0W1kECg

Какую под капотом реализует JavaScript sort - чорт его знает. Но возможно одна из самых быстрых.

Comments

[Михаил Оловянников]

Спасибо за ответ. Хотел еще спросить - может вы посоветуете книгу по алгоритмам или даже книгу для того, чтобы подготовится читать легкие книги по алгоритмам для совсем-совсем новичка (или видео-курс). Я как-то пробовал читать некоторые, но понял, что забытый курс математики заставляет смотреть даже на многие формулы как баран на ворота.

[mayton2019]

Михаил Оловянников, поищи Вирт - Алгоритмы и структуры данных. Она - хотя бы маленькая и не пугает новичков.

[shurshur]

Михаил Оловянников, можно например посмотреть сайт https://algolist.ru/ (автор тот же, что создал известный среди js-ников learn.javascript.ru).

[mayton2019]

shurshur, да хороший сайт. Но новички часто бывают перегружены хеш-тегами. Зачем изучать 20 сортировок - я не понимаю. Возьмите 3 штуки и хватит. Хоар. Пирамида. И Шелл.

Тоже самое алгоритмы хеширования. Вот просто мордуют бедных студентов расстановками. И квадратичные. И идеал хеш функции ищут. А ево все равно ни жуя нет. И какие-то прочие теоретические. Промышленность все равно берет один метод. Бакеты со списками и точка.

Answer 2

[alexalexes]

Вам не нужно знать как работает функция sort, вам нужно дать этой функции метод как "взвесить" любые два элемента списка, как оценить свойства или значение самого элемента, чтобы понять, какой из них должен идти впереди какого. Результат метода должен быть 1, 0 или -1.
Если 1, то A тяжелее B.
Если -1, то А легче B.
Если 0 - то элементы эквивалентны.

function(a,b)
{
  if(/*условие на A тяжелее B*/) // чашка A ниже чашки B на рычажных весах 
    return 1;
 else if(/*условие на A легче B*/) // чашка A выше чашки B на рычажных весах 
    return -1;
  else
  return 0; //иначе - эквиваленты, весы уравновешены
 // если условия на тяжесть и легкость поменять местами, то поменяется направление сортировки
}

Comments

[Михаил Оловянников]

Я понимаю смысл ее работы и как сделать функцию условие для того, чтобы она сортировала в любом порядка (по возрастанию или убыванию). Я не понимаю почему в b идет число 1. Например в этом видео: https://www.youtube.com/watch?v=O2pusOp0gC0 у человека в переменную а идет первое значение. Выходит эту функцию за эти 5 лет переделали?

[alexalexes]

Каждый движок браузера делает разные шаги - значит реализация сортировки разная.
Стандарт JS, скорее всего не диктует жестко, каким патентованным методом сортировать элементы.
Если разработчики движка хотят пузырьком сортировать - будет работать пузырьком, захотят оптимизировать метод - будет работать на чем-то стильном, модном, молодежном.

[Михаил Оловянников]

alexalexes, спасибо большое за ответ, теперь понял что не все так однообразно как мне казалось.

[Дмитрий Беляев]

Стандарт JS, скорее всего не диктует жестко, каким патентованным методом сортировать элементы.

alexalexes, кое-что все же диктует, со стандарта ES2019 допустимы только алгоритмы стабильной сортировки, то есть алгоритмы, которые сохраняют исходный порядок для равных элементов.

Answer 3

[Rsa97]

Открывайте исходники движка и изучайте, как разработчик реализовал сортировку. Даже в пределах одного движка могут быть реализованы несколько разных алгоритмов, в зависимости от размера массива и типа элементов.

Answer 4

[Mikhail Osher]

Array.prototype.sort specification

Однако там сложным языком описано.
На MDN в разделе Description описаны нюансы, которые могут быть полезны.