Какова стабильность метода Array.sort() в разных браузерах?

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

Я нашел эту информацию для Firefox, которая указывает, что Firefox использует стабильную сортировку.

Кто-нибудь знает про IE 6/7/8, Chrome и Safari?

Источник

5 ответов

Решение

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

Сортировка IE была стабильной до тех пор, пока я ее использовал (то есть IE6). Повторная проверка в IE8, и, похоже, все еще так.

И хотя эта страница Mozilla, на которую вы ссылаетесь, говорит о том, что сортировка Firefox стабильна, я определенно говорю, что это было не всегда до (и в том числе) до Firefox 2.0.

Некоторые краткие результаты:

  • IE6 +: стабильный
  • Firefox < 3: нестабильный
  • Firefox >= 3: стабильный
  • Хром < 70: нестабильно
  • Chrome >= 70: стабильный
  • Опера < 10: нестабильно
  • Опера>= 10: стабильный
  • Safari 4: стабильный
  • Край: нестабильный для длинных массивов

Все тесты на Windows.

Смотрите также: Быстрая стабильная реализация алгоритма сортировки в javascript

Источник

Я хотел бы поделиться трюком, который я обычно использую в C/C++ для qsort(),

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

function stableSorted(array, compareFunction) {
  compareFunction = compareFunction || defaultCompare;
  var indicies = new Array(array.length);
  for (var i = 0; i < indicies.length; i++)
    indicies[i] = i;

Это индексы в исходный массив. Мы собираемся отсортировать второй массив. Сделайте пользовательскую функцию сравнения.

  indicies.sort(function(a, b)) {

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

    var aValue = array[a], bValue = array[b];
    var order = compareFunction(a, b);
    if (order != 0)
      return order;

Если элементы оказываются равными, сравните их индексы, чтобы сделать порядок стабильным.

   if (a < b)
     return -1;
   else
     return 1;
  });

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

  var sorted = new Array(array.length);
  for (var i = 0; i < sorted.length; i++)
    sorted[i] = array[indicies[i]];
  return sorted;
}

// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
  a = String(a);
  b = String(b);
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
}

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

Источник

Начиная с V8 v7.0 и Chrome 70, наши Array.prototype.sort реализация сейчас стабильна.

Ранее V8 использовал нестабильную QuickSort для массивов с более чем 10 элементами. Теперь V8 использует стабильный алгоритм TimSort.

Единственный основной движок JavaScript, который до сих пор работает нестабильно Array#sort реализация чакры, как используется в Microsoft Edge. Чакра использует QuickSort для массивов с более чем 512 элементами. Для небольших массивов используется стабильная реализация сортировки вставками.

Демо: https://mathiasbynens.be/demo/sort-stability

Источник

В случае, если кто-то найдет это полезным, у меня был полифилл для этого, который я сейчас удаляю:

Источник

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

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

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

Вы можете отправить патч на http://www.browserscope.org/ чтобы включить такие тесты в свой комплект. Но опять же, функция обнаружения превосходит обнаружение браузера.

Источник
Другие вопросы по тегам