Почему сортировка массива JS чисел с <work?

Ответ 1

Эта сортировка работает с вашим входным массивом из-за его небольшого размера и текущей реализации sort в Chrome V8 (и, вероятно, других браузерах).

Возвращаемое значение функции компаратора определено в документации:

• Если compareFunction(a, b) меньше 0, сортировать с индексом ниже a b, то есть a первом месте.
• Если compareFunction(a, b) возвращает 0, оставьте a и b неизменными по отношению друг к другу, но отсортированные по всем различным элементам.
• Если compareFunction(a, b) больше 0, сортировка b выполняется по индексу ниже, чем a, т.е. b идет первым.

Однако ваша функция возвращает двоичное значение true или false, которые оцениваются в 1 или 0 соответственно по сравнению с числом. Это эффективно объединяет сравнения, где n1 < n2 с n1 === n2, утверждая, что оба являются четными. Если n1 равно 9 и n2 равно 3, 9 < 3 === false или 0. Другими словами, ваша сортировка оставляет 9 и 3 "неизменными по отношению друг к другу", а не настаивает на "сортировке 9 с индексом ниже 3".

Если ваш массив короче 11 элементов, процедура сортировки Chrome V8 немедленно переключается на сортировку вставкой и не выполняет быстрых шагов сортировки:

// Insertion sort is faster for short arrays.
if (to - from <= 10) {
  InsertionSort(a, from, to);
  return;
}

Реализация сортировки вставки V8 заботится только о том, что функция сравнения сообщает, что b больше, чем a, принимая одну и ту же ветвь else для 0 и < 0 возвращаемых значений компаратора:

var order = comparefn(tmp, element);
if (order > 0) {
  a[j + 1] = tmp;
} else {
  break;
}

Реализация быстрой сортировки, однако, опирается на все три сравнения как при выборе сводки, так и при разбиении:

var order = comparefn(element, pivot);
if (order < 0) {
  // ...
} else if (order > 0) {
  // ...
}
// move on to the next iteration of the partition loop

Это гарантирует точную сортировку на массивах, таких как [1,3,2,4], и обрекает массивы с более чем 10 элементами по крайней мере на один почти наверняка неточный шаг быстрой сортировки.

Обновление 19/19/19: Так как версия V8 (6) обсуждалась в этом ответе, реализация сортировки массива V8 перемещена в Torque/Timsort в 7.0, как обсуждалось в этом сообщении в блоге, и сортировка вставки вызывается для массивов длиной 22 или менее,

В статье, приведенной выше, описывается историческая ситуация сортировки V8, существовавшая на момент вопроса:

Array.prototype.sort и TypedArray.prototype.sort полагались на одну и ту же реализацию Quicksort, написанную на JavaScript. Сам алгоритм сортировки довольно прост: основа - быстрая сортировка с запасным вариантом сортировки вставкой для более коротких массивов (длина <10). Откат Insertion Sort также использовался, когда рекурсия Quicksort достигла длины подмассива 10. Сортировка вставки более эффективна для небольших массивов. Это потому, что Quicksort вызывается рекурсивно дважды после разбиения. Каждый такой рекурсивный вызов создавал (и отбрасывал) кадр стека.

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

Ответ 2

Если мы проанализируем, что делается, кажется, что это в основном удача, поскольку в этом случае 3 и 2 считаются "одинаковыми" и должны быть взаимозаменяемыми. Я полагаю, что в таких случаях двигатели JS сохраняют первоначальный порядок для любых значений, которые считаются равными:

let a = [1, 3, 2, 4];
a.sort((n1, n2) => {
  const result = n1 < n2;
  if (result < 0) {
    console.log('${n1} comes before ${n2}');
  } else if (result > 0) {
    console.log('${n2} comes before ${n1}');
  } else {
    console.log('${n1} comes same position as ${n2}');
  }
  return result;
})

console.log(a);

Ответ 3

После моего первоначального комментария я немного подумал о том, как легко найти массивы, для которых этот метод сортировки терпит неудачу.

Я провел исчерпывающий поиск по массивам длиной до 8 (на алфавите размером с размер массива) и ничего не нашел. Поскольку мой (по общему признанию shitty) алгоритм стал слишком медленным, я изменил его на алфавит размером 2 и обнаружил, что двоичные массивы длиной до 10 отсортированы правильно. Однако для двоичных массивов длиной 11 многие неправильно отсортированы, например [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0].

// Check if 'array' is properly sorted using the "<" comparator function
function sortWorks(array) {
    let sorted_array = array.sort(function(n1, n2) {
        return n1 < n2;
    });
    for (let i=0; i<sorted_array.length-1; i++) {
        if (sorted_array[i] < sorted_array[i+1]) return false;
    }
    return true;
}

// Get a list of all arrays of length 'count' on an alphabet of size 'max_n'.
// I know it awful, don't yell at me :'(
var arraysGenerator;
arraysGenerator = function (max_n, count) {
    if (count === 0) return [[]];
    let arrays = arraysGenerator(max_n, count-1);
    let result = [];
    for (let array of arrays) {
        for (let i = 0; i<max_n; i++) {
            result.push([i].concat(array));
        }
    }
    return result;
}

// Check if there are binary arrays of size k which are improperly sorted,
// and if so, log them
function testArraysOfSize(k) {
    let arrays = arraysGenerator(2, k);
    for (let array of arrays) {
        if (!sortWorks(array)) {
            console.log(array);
        }
    }
}

По некоторым причинам я получаю некоторые странные ложные срабатывания, хотя не знаю, где моя ошибка.

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

После проверки на некоторое время, здесь частичное объяснение того, почему OP "неправильный" метод сортировки работает для длин <= 10 и для lengths> = 11: он выглядит (по крайней мере, некоторые) реализации javascript используют InsertionSort, если длина массива коротка (длина <= 10) и QuickSort в противном случае. Похоже, QuickSort активно использует "-1" выходы функции сравнения, а InsertionSort не использует и использует только "1" выходы.

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

Ответ 4

В зависимости от точной реализации sort(), вероятно, он никогда не проверяет -1. Это проще и быстрее, и это не имеет значения (поскольку сортировка не гарантируется в любом случае стабильной, IIRC).

Если check sort() делает внутренне - compareFunction(a, b) > 0, то эффективно true интерпретируется как a > b, а false интерпретируется как a <= b. И тогда ваш результат - именно то, чего можно было бы ожидать.

Разумеется, ключевым моментом является то, что для > сравнения true получает значение 1, а false - 0.

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

Ответ 5

Функция сортировки ожидает компаратор, который возвращает число (отрицательное, ноль или положительное).

Предполагая, что вы работаете поверх движка V8 (Node.js, Chrome и т.д.), Вы можете найти в реализации массива, что возвращаемое значение сравнивается с 0 (yourReturnValue > 0). В этом случае возвращаемое значение передается на число, поэтому:

• Значения Truthy преобразуются в 1
• Значения Falsy преобразуются в 0

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