logicface
@logicface
Начинающий

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

Запутался в сортировке .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. Как этот алгоритм работает я что-то вообще не понимаю. Можете пошагово объяснить, как он в массиве меняет значения и почему это все так?
  • Вопрос задан
  • 207 просмотров
Решения вопроса 2
mayton2019
@mayton2019
Bigdata Engineer
Поскольку вопрос тегирован алгоритмами - человек пытается ИХ изучать а не контракт array.sort.

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

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

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

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

Какую под капотом реализует JavaScript sort - чорт его знает. Но возможно одна из самых быстрых.
Ответ написан
@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; //иначе - эквиваленты, весы уравновешены
 // если условия на тяжесть и легкость поменять местами, то поменяется направление сортировки
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Открывайте исходники движка и изучайте, как разработчик реализовал сортировку. Даже в пределах одного движка могут быть реализованы несколько разных алгоритмов, в зависимости от размера массива и типа элементов.
Ответ написан
Комментировать
miraage
@miraage
Старый прогер
Array.prototype.sort specification

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы