Как метод родной сортировки работает с разреженными массивами

Question

Когда сортируется разреженный массив [5, 2, 4, , 1].sort() -> [1, 2, 4, 5, empty], пустое значение всегда остается последним даже с обратным вызовом, независимо от оператора return.

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

const collectUndefined = [];

// remove empty items and collect undefined
const removeSparse = this.filter(el => {
  if (el === undefined) {
    collectUndefined.push(el);
  }

  return el !== undefined;
});

const tempLength = this.length;

// reset values but will contain duplicates at the end
for (let i = 0; i < removeSparse.length; i++) {
  this[i] = removeSparse[i];
}

// shorten length which will remove extra duplicates
this.length = removeSparse.length;



// sort algorithm ...



// place undefineds back into the array at the end
this.push(...collectUndefined);

// restores original length and add empty elemnts at the end
this.length = tempLength;
return this

Реализуется ли подобная родная сортировка таким же образом при работе с разреженными массивами, или нет.

Answer 1

Когда дело доходит до реализации Array.sort, вы также должны спросить, какой движок? Они не все равны с точки зрения , как они в конечном итоге попадают в окончательную sorted версию массива. Например, V8 имеет этап предварительной обработки и последующей обработки перед any сортировкой:

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

Вы можете найти довольно подробное объяснение всего процесса V8 проходит здесь

Фактический исходный код для сортировки V8 (с использованием Timsort ) может быть найден здесь и теперь находится на языке Torque .

JS тесты для V8 Array.sort могут быть здесь видно

Суть в том, что на самом деле ничего не удаляется из исходного массива, поскольку этого не должно быть. Сортировка не должна mutate исходный массив. Это было бы супер weird, если вы позвоните myArray.sort(), и вдруг у него будет на 5 элементов меньше, чем из 8 (например). Это не то, что вы найдете в любых Array.sort спецификациях.

Также Array.sort уделяет пристальное внимание сортируемым типам и заказывает их специально. Пример:

let arr = [4,2,5,,,,3,false,{},undefined,null,0,function(){},[]]

console.log(arr.sort())

Обратите внимание на вывод выше, как сначала array, затем значения numeric, object literal, Boolean, function, null, а затем undefined / empty. Поэтому, если вы хотите действительно соответствовать спецификации, вам следует подумать о том, как сортируются разные типы.