Как работает Javascript sort ()?

Как следующий код сортирует этот массив по порядку номеров?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

Я знаю, что если результат вычисления ...

Меньше 0 : индекс «a» отсортирован по более низкому индексу, чем «b».
Ноль: «a» и «b» считаются равными, сортировка не выполняется.
Больше 0: «b» отсортировано как более низкий индекс, чем «a».

Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?

Если да, то я хотел бы знать, какие два числа каждый раз передаются в функцию. Я предположил, что сначала нужно взять «25» (а) и «8» (б), а затем «7» (а) и «41» (б), поэтому:

25 (a) - 8 (b) = 17 (больше нуля, поэтому отсортируйте "b" так, чтобы индекс был ниже, чем "a"): 8, 25

7 (a) - 41 (b) = -34 (меньше нуля, поэтому отсортируйте "a" так, чтобы индекс был ниже, чем "b": 7, 41

Как тогда эти два набора чисел сортируются по отношению друг к другу?

Пожалуйста, помогите начинающему новичку!

Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?

да

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

Вы можете узнать себя с помощью:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

РЕДАКТИРОВАТЬ

Вот результат, который у меня есть:

25,8
25,7
8,7
25,41

Интерпретатор JavaScript имеет встроенную реализацию алгоритма сортировки . Он вызывает функцию сравнения несколько раз во время операции сортировки. Количество вызовов функции сравнения зависит от конкретного алгоритма, сортируемых данных и порядка их расположения до сортировки.

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

Существует множество широко используемых алгоритмов сортировки, потому что ни один алгоритм не подходит для всех целей. Два наиболее часто используемых для общей сортировки - это быстрая сортировка и сортировка слиянием . Быстрая сортировка часто является более быстрой из двух, но сортировка слиянием имеет несколько хороших свойств, которые могут сделать ее лучшим выбором в целом. Сортировка слиянием стабильна , а Quicksort - нет. Оба алгоритма можно распараллелить, но способ сортировки слиянием делает параллельную реализацию более эффективной при прочих равных.

Ваш конкретный интерпретатор JavaScript может использовать один из этих алгоритмов или что-то совсем другое. ECMAScript стандарт не определяет , какой алгоритм полной реализация должна использовать. Он даже явно отрицает необходимость стабильности.

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

При использовании сортировки JavaScript следует помнить, что ее стабильность не гарантируется.

Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?

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

Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки?

Поскольку это сортировка сравнения, для данных N элементов функцию обратного вызова следует вызывать в среднем (N * Lg N) раз для быстрой сортировки, такой как Quicksort . Если используемый алгоритм похож на пузырьковую сортировку , то функция обратного вызова будет вызываться в среднем (N * N) раз.

Минимальное количество вызовов для сортировки сравнения составляет (N-1), и это только для обнаружения уже отсортированного списка (т.е. на ранней стадии пузырьковой сортировки, если не происходит перестановок).

Глубокое знание

Если результат отрицательный, a сортируется перед b.

Если результат положительный, b сортируется перед a.

Если результат равен 0, то порядок сортировки двух значений не изменяется.

НОТА:

Этот код представляет собой пошаговое представление внутри метода сортировки .

ВЫХОД:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();		//create duplicate array
var inc = 0;	//inc meant increment
copy.sort((a, b) => {
	sortRes[inc] = [ a, b, a-b ];
	inc += 1;
	return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
	copy = arr.slice();
	copy.sort((a, b) => {
		p += 1;
		if (p <= i ) {
			return a - b;
		}
		else{
			return false;
		}
	});
	p = 0;
	console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}

запустите этот код. Вы можете увидеть точный пошаговый процесс сортировки от начала до конца.

var array=[25, 8, 7, 41]
var count = 1;
array.sort( (a,b) => { 
console.log(`${count++}). a: ${a} | b: ${b}`);
return a-b;
});
console.log(array);

Чтобы помочь прояснить поведение Array#sortи его компаратор, рассмотрим эту наивную сортировку вставки, которую преподают в начальных курсах программирования:

const sort = arr => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && arr[j-1] > arr[j]; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);

Не обращая внимания на выбор вставки рода в качестве алгоритма, фокуса на закодированном компараторе: arr[j-1] > arr[j]. Здесь есть две проблемы, относящиеся к обсуждению:

1. >Оператор вызывается на пары элементов массива , но многие вещи , которые вы , возможно , захотите сортировать такие как объекты не отвечают >в разумных пределах (то же самое было бы верно , если бы мы использовали -).
2. Даже если вы работаете с числами, часто вам нужно другое расположение, а не сортировка по возрастанию, которая здесь используется.

Мы можем решить эти проблемы, добавив comparefnзнакомый вам аргумент:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);

sort(array, (a, b) => b - a);
console.log("" + array);

const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));

Теперь наивная процедура сортировки обобщена. Вы можете точно увидеть, когда вызывается этот обратный вызов, отвечая на ваш первый набор проблем:

Вызывается ли функция обратного вызова сортировки массива много раз в ходе сортировки? Если да, то я хотел бы знать, какие два числа передаются в функцию каждый раз.

Выполнение приведенного ниже кода показывает, что да, функция вызывается много раз, и вы можете использовать ее, console.logчтобы увидеть, какие числа были переданы:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);

console.log("on the builtin:");
console.log("" + 
  [3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);

Ты спрашиваешь:

Как тогда эти два набора чисел сортируются по отношению друг к другу?

Чтобы быть точным , с терминологией, aа bне наборы чисел - they're объекты в массиве (в вашем примере, они номер).

По правде говоря, не имеет значения, как они отсортированы, потому что это зависит от реализации. Если бы я использовал другой алгоритм сортировки, чем сортировка вставкой, компаратор, вероятно, вызывался бы для разных пар чисел, но в конце вызова сортировки инвариант, который имеет значение для программиста JS, заключается в том, что массив результатов сортируется в соответствии с компаратор, предполагая, что компаратор возвращает значения, которые соответствуют указанному вами контракту (<0, когда a < b, 0, когда a === bи> 0, когдаa > b ).

В том же смысле, что у меня есть свобода изменять свою реализацию сортировки до тех пор, пока я не нарушаю свою спецификацию, реализации ECMAScript могут свободно выбирать реализацию сортировки в пределах спецификации языка , поэтому Array#sort, вероятно, будут создаваться разные вызовы компаратора на разных двигателях. Нельзя писать код, в котором логика полагается на некоторую конкретную последовательность сравнений (и компаратор не должен вызывать побочные эффекты в первую очередь).

Например, механизм V8 (на момент написания) вызывает Timsort, когда массив больше, чем некоторое предварительно вычисленное количество элементов, и использует сортировку двоичной вставкой для небольших фрагментов массива. Однако раньше он использовал быструю сортировку, которая нестабильна и, вероятно, дает другую последовательность аргументов и вызовов компаратору.

Поскольку разные реализации сортировки по-разному используют возвращаемое значение функции компаратора, это может привести к неожиданному поведению, когда компаратор не соблюдает контракт. См. Эту ветку для примера.

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  console.log(`a = ${a} , b = ${b}`);
  return a - b
});

ВЫХОД

• а = 8, б = 25
• а = 7, б = 8
• а = 41, б = 7
• а = 41, б = 8
• а = 41, б = 25

в моем браузере (Google Chrome версии 70.0.3538.77 (официальная сборка) (64-разрядная версия)) в первой итерации аргумент a является вторым элементом в массиве, а аргумент b является первым элементом массива.

если функция сравнения возвращает

1. Отрицательное значение, чем b, перемещается вперед к a.
2. положительное значение, чем a перемещается вперед в b.
3. 0 (ноль) и a, и b останутся как есть.