정렬 된 숫자 배열에 숫자를 삽입하는 효율적인 방법?

정렬 된 숫자 배열에 숫자를 삽입하는 효율적인 방법?

---

정렬 된 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 (n)보다 훨씬 큰 계수를 갖는 O (log (n))가 여전히 더 나쁩니다.

---

단일 데이터 포인트와 마찬가지로, 킥을 위해 Windows 7에서 Chrome을 사용하는 두 가지 방법을 사용하여 1000 개의 임의 요소를 10 개의 사전 정렬 된 숫자 배열에 삽입하여이를 테스트했습니다.

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

따라서 적어도이 설정에서 기본 방법은 그것을 보완하지 못합니다. 작은 데이터 세트의 경우에도 1000 개의 배열에 100 개의 요소를 삽입합니다.

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

이 수정이 없으면 코드는 배열의 시작 부분에 요소를 삽입 할 수 없습니다.

---

삽입 함수는 주어진 배열이 정렬되었다고 가정하고, 일반적으로 배열의 몇 가지 요소 만보고 새 요소를 삽입 할 수있는 위치를 직접 검색합니다.

The general sort function of an array can't take these shortcuts. Obviously it at least has to inspect all elements in the array to see if they are already correctly ordered. This fact alone makes the general sort slower than the insertion function.

A generic sort algorithm is usually on average O(n ⋅ log(n)) and depending on the implementation it might actually be the worst case if the array is already sorted, leading to complexities of O(n²). Directly searching for the insertion position instead has just a complexity of O(log(n)), so it will always be much faster.

---

I know this is an old question that has an answer already, and there are a number of other decent answers. I see some answers that propose that you can solve this problem by looking up the correct insertion index in O(log n) - you can, but you can't insert in that time, because the array needs to be partially copied out to make space.

Bottom line: If you really need O(log n) inserts and deletes into a sorted array, you need a different data structure - not an array. You should use a B-Tree. The performance gains you will get from using a B-Tree for a large data set, will dwarf any of the improvements offered here.

If you must use an array. I offer the following code, based on insertion sort, which works, if and only if the array is already sorted. This is useful for the case when you need to resort after every insert:

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

It should operate in O(n), which I think is the best you can do. Would be nicer if js supported multiple assignment. here's an example to play with:

Update:

this might be faster:

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

Updated JS Bin link

---

Here are a few thoughts: Firstly, if you're genuinely concerned about the runtime of your code, be sure to know what happens when you call the built-in functions! I don't know up from down in javascript, but a quick google of the splice function returned this, which seems to indicate that you're creating a whole new array each call! I don't know if it actually matters, but it is certainly related to efficiency. I see that Breton, in the comments, has already pointed this out, but it certainly holds for whatever array-manipulating function you choose.

Anyways, onto actually solving the problem.

When I read that you wanted to sort, my first thought is to use insertion sort!. It is handy because it runs in linear time on sorted, or nearly-sorted lists. As your arrays will have only 1 element out of order, that counts as nearly-sorted (except for, well, arrays of size 2 or 3 or whatever, but at that point, c'mon). Now, implementing the sort isn't too too bad, but it is a hassle you may not want to deal with, and again, I don't know a thing about javascript and if it will be easy or hard or whatnot. This removes the need for your lookup function, and you just push (as Breton suggested).

Secondly, your "quicksort-esque" lookup function seems to be a binary search algorithm! It is a very nice algorithm, intuitive and fast, but with one catch: it is notoriously difficult to implement correctly. I won't dare say if yours is correct or not (I hope it is, of course! :)), but be wary if you want to use it.

Anyways, summary: using "push" with insertion sort will work in linear time (assuming the rest of the array is sorted), and avoid any messy binary search algorithm requirements. I don't know if this is the best way (underlying implementation of arrays, maybe a crazy built-in function does it better, who knows), but it seems reasonable to me. :) - Agor.

---

For a small number of items, the difference is pretty trivial. However, if you're inserting a lot of items, or working with a very large array, calling .sort() after each insertion will cause a tremendous amount of overhead.

I ended up writing a pretty slick binary search/insert function for this exact purpose, so I thought I'd share it. Since it uses a while loop instead of recursion, there is no overheard for extra function calls, so I think the performance will be even better than either of the originally posted methods. And it emulates the default Array.sort() comparator by default, but accepts a custom comparator function if desired.

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

If you're open to using other libraries, lodash provides sortedIndex and sortedLastIndex functions, which could be used in place of the while loop. The two potential downsides are 1) performance isn't as good as my method (thought I'm not sure how much worse it is) and 2) it does not accept a custom comparator function, only a method for getting the value to compare (using the default comparator, I assume).

---

Here's a comparison of four different algorithms for accomplishing this: https://jsperf.com/sorted-array-insert-comparison/1

Algorithms

• Naive: just push and sort() afterwards
• Linear: iterate over array and insert where appropriate
• Binary Search: taken from https://stackoverflow.com/a/20352387/154329
• "Quick Sort Like": the refined solution from syntheticzero (https://stackoverflow.com/a/18341744/154329)

Naive is always horrible. It seems for small array sizes, the other three dont differ too much, but for larger arrays, the last 2 outperform the simple linear approach.

---

Here's a version that uses lodash.

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

note: sortedIndex does a binary search.

---

Don't re-sort after every item, its overkill..

If there is only one item to insert, you can find the location to insert using binary search. Then use memcpy or similar to bulk copy the remaining items to make space for the inserted one. The binary search is O(log n), and the copy is O(n), giving O(n + log n) total. Using the methods above, you are doing a re-sort after every insertion, which is O(n log n).

Does it matter? Lets say you are randomly inserting k elements, where k = 1000. The sorted list is 5000 items.

• 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

If the k items to insert arrive whenever, then you must do search+move. However, if you are given a list of k items to insert into a sorted array - ahead of time - then you can do even better. Sort the k items, separately from the already sorted n array. Then do a scan sort, in which you move down both sorted arrays simultaneously, merging one into the other. - One-step Merge sort = k log k + n = 9965 + 5000 = ~15,000 ops

Update: Regarding your question.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n) Exactly explains the timings you're getting.

---

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

참고URL : https://stackoverflow.com/questions/1344500/efficient-way-to-insert-a-number-into-a-sorted-array-of-numbers