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

У меня есть отсортированный массив 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) для наборов данных разумного размера.

Как и отдельная точка данных, я испытал это на практике, вставив 1000 случайных элементов в массив из 100000 предварительно отсортированных чисел, используя два метода с использованием Chrome в Windows 7:

First Method:
~54 milliseconds
Second Method:
~57 seconds

Так что, по крайней мере, в этой настройке собственный метод не компенсирует это. Это верно даже для небольших наборов данных, когда 100 элементов вставляются в массив из 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

Простой ( Демо ):

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

Очень хороший и замечательный вопрос с очень интересным обсуждением! Я также использовал эту Array.sort()функцию после нажатия одного элемента в массиве с несколькими тысячами объектов.

Мне пришлось расширить вашу locationOfфункцию для моей цели из-за наличия сложных объектов и, следовательно, необходимости в функции сравнения, например Array.sort():

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};

В вашем коде есть ошибка. Он должен читать:

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

Без этого исправления код никогда не сможет вставить элемент в начало массива.

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

Итог: если вам действительно нужно O (log n) вставлять и удалять в отсортированный массив, вам нужна другая структура данных, а не массив. Вам следует использовать B-Tree . Прирост производительности, который вы получите от использования B-Tree для большого набора данных, затмит любые из предлагаемых здесь улучшений.

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

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

Он должен работать в O (n), что, я думаю, лучшее, что вы можете сделать. Было бы лучше, если бы js поддерживал множественное назначение. вот пример для игры:

Обновить:

это может быть быстрее:

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

Обновленная ссылка JS Bin

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

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

Общий алгоритм сортировки обычно составляет в среднем O (n ⋅ log (n)), и в зависимости от реализации это может быть наихудший случай, если массив уже отсортирован, что приводит к сложности O (n ² ) . Вместо этого прямой поиск позиции вставки имеет сложность O (log (n)) , поэтому он всегда будет намного быстрее.

Вот несколько мыслей: Во-первых, если вы искренне обеспокоены временем выполнения вашего кода, обязательно знайте, что происходит, когда вы вызываете встроенные функции! Я не знаю, вверх и вниз в javascript, но быстрый гугл функции splice вернул это , что, кажется, указывает на то, что вы создаете совершенно новый массив при каждом вызове! Не знаю, действительно ли это имеет значение, но, безусловно, связано с эффективностью. Я вижу, что Бретон в комментариях уже указывал на это, но это определенно справедливо для любой выбранной вами функции управления массивами.

В любом случае, к фактическому решению проблемы.

Когда я прочитал, что вы хотите отсортировать, моя первая мысль - использовать сортировку вставкой! . Это удобно, потому что он работает в линейном времени в отсортированных или почти отсортированных списках . Поскольку в ваших массивах будет только 1 неупорядоченный элемент, который считается почти отсортированным (за исключением, ну, массивов размера 2 или 3 или чего-то еще, но в этот момент давай). Теперь реализация сортировки не так уж и плоха, но это проблема, с которой вы, возможно, не захотите иметь дело, и, опять же, я ничего не знаю о javascript и будет ли это легко или сложно или еще много чего. Это устраняет необходимость в вашей функции поиска, и вы просто нажимаете (как предложил Бретон).

Во-вторых, ваша функция поиска в стиле быстрой сортировки, похоже, является алгоритмом двоичного поиска ! Это очень хороший алгоритм, интуитивно понятный и быстрый, но с одной загвоздкой: его, как известно, сложно реализовать правильно. Я не осмелюсь сказать, верна ваша или нет (надеюсь, конечно! :)), но будьте осторожны, если хотите ее использовать.

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

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

В итоге я написал довольно удобную функцию двоичного поиска / вставки именно для этой цели, поэтому решил поделиться ею. Поскольку whileвместо рекурсии используется цикл, дополнительные вызовы функций не подслушиваются, поэтому я думаю, что производительность будет даже лучше, чем у любого из первоначально опубликованных методов. И он имитирует Array.sort()компаратор по умолчанию по умолчанию, но при желании принимает настраиваемую функцию компаратора.

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

Если вы открыты для использования других библиотек, lodash предоставляет функции sortedIndex и sortedLastIndex , которые можно использовать вместо whileцикла. Два потенциальных недостатка: 1) производительность не так хороша, как у моего метода (я не уверен, насколько он хуже) и 2) он не принимает настраиваемую функцию компаратора, а только метод получения значения для сравнения (я полагаю, используя компаратор по умолчанию).

Вот сравнение четырех разных алгоритмов для этого: https://jsperf.com/sorted-array-insert-comparison/1

Алгоритмы

• Наивный: просто нажмите и затем выполните sort ()
• Линейный: перебрать массив и вставить, где это необходимо
• Двоичный поиск: взято из https://stackoverflow.com/a/20352387/154329
• «Быстрая сортировка по типу»: усовершенствованное решение от синтетического нуля ( https://stackoverflow.com/a/18341744/154329 )

Наивный всегда ужасен. Кажется, что для небольших размеров массивов остальные три не слишком сильно отличаются, но для больших массивов последние 2 превосходят простой линейный подход.

Вот версия, в которой используется lodash.

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

примечание: sortedIndex выполняет двоичный поиск.

Лучшая структура данных, о которой я могу думать, - это индексированный список пропуска, который поддерживает свойства вставки связанных списков с иерархической структурой, которая позволяет выполнять операции записи времени. В среднем поиск, вставка и поиск произвольного доступа могут выполняться за время O (log n).

Порядок статистика дерево позволяет время индексации журнала с функцией ранга.

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

Ни один из используемых ответов не array.splice()является эффективным, поскольку в среднем это время O (n). Какова временная сложность array.splice () в Google Chrome?

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

function binaryInsert(val, arr){
    let mid, 
    len=arr.length,
    start=0,
    end=len-1;
    while(start <= end){
        mid = Math.floor((end + start)/2);
        if(val <= arr[mid]){
            if(val >= arr[mid-1]){
                arr.splice(mid,0,val);
                break;
            }
            end = mid-1;
        }else{
            if(val <= arr[mid+1]){
                arr.splice(mid+1,0,val);
                break;
            }
            start = mid+1;
        }
    }
    return arr;
}

console.log(binaryInsert(16, [
    5,   6,  14,  19, 23, 44,
   35,  51,  86,  68, 63, 71,
   87, 117
 ]));

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

Если нужно вставить только один элемент, вы можете найти место для вставки с помощью двоичного поиска. Затем используйте 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 = ~ 15 000 операций в секунду

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

Версия TypeScript с настраиваемым методом сравнения:

const { compare } = new Intl.Collator(undefined, {
  numeric: true,
  sensitivity: "base"
});

const insert = (items: string[], item: string) => {
    let low = 0;
    let high = items.length;

    while (low < high) {
        const mid = (low + high) >> 1;
        compare(items[mid], item) > 0
            ? (high = mid)
            : (low = mid + 1);
    }

    items.splice(low, 0, item);
};

Использование:

const items = [];

insert(items, "item 12");
insert(items, "item 1");
insert(items, "item 2");
insert(items, "item 22");

console.log(items);

// ["item 1", "item 2", "item 12", "item 22"]

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;
}