Эффективный способ вставить число в отсортированный массив чисел? - PullRequest
Новая
       12

Эффективный способ вставить число в отсортированный массив чисел?

113 голосов
/ 28 августа 2009

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

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

[ПРЕДУПРЕЖДЕНИЕ] этот код содержит ошибку при попытке вставить в начало массива, например, insert(2, [3, 7 ,9]) выдает некорректно [3, 2, 7, 9].

Однако я заметил, что реализации функции Array.sort потенциально могут сделать это для меня, и изначально: 

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

Есть ли веская причина выбирать первую реализацию вместо второй?

Редактировать : обратите внимание, что для общего случая вставка O (log (n)) (как реализовано в первом примере) будет быстрее, чем общий алгоритм сортировки; однако это не обязательно относится к JavaScript в частности. Обратите внимание:

  • Наилучшим случаем для нескольких алгоритмов вставки является O (n), который все еще значительно отличается от O (log (n)), но не так плохо, как O (n log (n)), как упомянуто ниже. Все сводится к конкретному алгоритму сортировки (см. Реализация Javascript Array.sort? )
  • Метод сортировки в JavaScript является встроенной функцией, поэтому потенциально может принести огромные преимущества - O (log (n)) с огромным коэффициентом может быть намного хуже, чем O (n) для наборов данных разумного размера.

Ответы [ 12 ]

0 голосов
/ 23 июля 2017 
function insertOrdered(array, elem) {
    let _array = array;
    let i = 0;
    while ( i < array.length && array[i] < elem ) {i ++};
    _array.splice(i, 0, elem);
    return _array;
}
0 голосов
/ 24 июля 2012

Не пересортируйте после каждого предмета, его перебор.

Если есть только один элемент для вставки, вы можете найти место для вставки, используя бинарный поиск. Затем используйте memcpy или аналогичное для массового копирования оставшихся элементов, чтобы освободить место для вставленного. Двоичный поиск - O (log n), а копия - O (n), что дает O (n + log n) всего. Используя методы выше, вы делаете повторную сортировку после каждой вставки, которая является O (n log n).

Это имеет значение? Допустим, вы случайным образом вставляете k элементов, где k = 1000. Сортированный список составляет 5000 элементов.

  • Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
  • Re-sort on each = k*(n log n) = ~60 million ops

Если k элементов для вставки поступает всякий раз, тогда вы должны выполнить поиск + перемещение. Однако, если вам дается список из k элементов для вставки в отсортированный массив - заблаговременно - тогда вы можете сделать еще лучше. Сортировать k элементов отдельно от уже отсортированного массива n. Затем выполните сортировку сканирования, в которой вы перемещаете оба отсортированных массива одновременно, сливая один в другой. - Одношаговая сортировка слиянием = k log k + n = 9965 + 5000 = ~ 15000 операций

Обновление: по вашему вопросу.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n) Точно объясняет время, которое вы получаете.

Страница:
...