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

Ответ 1

Простой тестовый пример (игнорируйте заголовок, второй набор чисел должен быть последовательным, если сортировка двигателя стабильна). Примечание: этот тестовый пример не работает для некоторых версий Chrome (технически, V8), которые переключали алгоритмы сортировки на основе размера массива, используя стабильную сортировку для небольших массивов, но нестабильную для больших массивов. (Подробности.) См. Конец вопроса об измененной версии, которая делает массив достаточно большим, чтобы вызвать поведение.

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

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

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

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

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

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

Тестовый пример, который продемонстрирует проблему в V8 (например, Node v6, Chrome <v70):

function Pair(_x, _y) {
    this.x = _x;
    this.y = _y;
}
function pairSort(a, b) {
    return a.x - b.x;
}
var y = 0;
var check = [];
while (check.length < 100) {
    check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));
}
check.sort(pairSort);
var min = {};
var issues = 0;
for (var i = 0; i < check.length; ++i) {
    var entry = check[i];
    var found = min[entry.x];
    if (found) {
        if (found.y > entry.y) {
            console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);
            ++issues;
        }
    } else {
        min[entry.x] = {x: entry.x, y: entry.y, i: i};
    }
}
if (!issues) {
    console.log("Sort appears to be stable");
}

Ответ 2

Я хотел бы поделиться трюком, который я обычно использую в 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;
}

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

Ответ 3

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

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

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

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

Ответ 4

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

Вместо этого выполните проверку сортировки сортировки, когда script загрузится и примет ваше решение.

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

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