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

정렬 된 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]있습니다.

그러나 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))가 여전히 더 나쁠 수 있습니다.

답변

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

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

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

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

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

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