Можете ли вы отсортировать натуральные числа за O (N) (линейное) время, используя объект в JavaScript?

Question

Мне нужно отсортировать массив натуральных чисел. Это достаточно просто сделать с помощью метода сортировки JavaScript в O (N * log (N)):

let a = [4, 1, 3, 9, 7, 19, 11];
a.sort((a,b) => a - b);
return a;

// returns [1, 3, 4, 7, 9, 11, 19]

Но, похоже, это можно сделать в O (N) с помощью JavaScript объект? Цикл по массиву для добавления целого числа в объект - это O (N), затем захват значений из этого объекта также равен O (N). (В качестве альтернативы возьмите ключи и конвертируйте обратно в числа).

let o = {};
let a = [4, 1, 3, 9, 7, 19, 11];

a.forEach(integer => { o[integer] = integer });

return Object.values(o);

// returns [1, 3, 4, 7, 9, 11, 19]

Удалите константу, и мы смотрим на сортировку натуральных чисел в O (N) (жертвуя дополнительным пространством O (N)). Из всего, что я прочитал, это не должно быть возможным. Что мне здесь не хватает?

Answer 1

Внутренний код, используемый для установки и получения ключей, зависит от реализации. Выход (и порядок) гарантирован (для всех методов перечисления свойств, начиная с ES2020 ), но механизм зависит от реализатора. Вам придется взглянуть на исходный код двигателя для этого.

Я не знаю код, по которому различные двигатели Javascript работают под капотом, но если вы знаете верхнюю границу для число в массиве, это это возможно в O(n) (или, точнее, O(n + k), где k - это константа - верхняя граница) с помощью сортировки счетом: создайте карту ключей (аналогично тому, как вы это делаете, но с учетом количества раз, которое появляется каждый элемент), затем выполните итерацию от 0 до верхней границы, проверяя, включено ли число, которое повторяется, в ключах. Если это так, pu sh в массив:

let o = {};
let a = [4, 1, 3, 9, 7, 19, 11];

// O(n)
for (const num of a) {
  if (!o[num]) {
    o[num] = [];
  }
  o[num].push(num);
}

// O(n). This part isn't strictly necessary, but the alternative makes the code uglier
const max = Math.max(...a);
const result = [];
// O(k)
for (let i = 0; i <= max; i++) {
  if (o[i]) {
    // total of O(n) items pushed over the whole loop
    result.push(...o[i]);
  }
}

console.log(result);

Если, как и в вашем примере, повторяющихся чисел нет, код значительно упрощается:

let o = {};
let a = [4, 1, 3, 9, 7, 19, 11];

for (const num of a) {
  o[num] = true;
}

// O(n)
const max = Math.max(...a);
const result = [];
// O(k)
for (let i = 0; i <= max; i++) {
  if (o[i]) {
    // total of O(n) items pushed over the whole loop
    result.push(i);
  }
}

console.log(result);