정렬 된 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))가 여전히 더 나쁠 수 있습니다.
답변
단일 데이터 포인트와 마찬가지로, 킥을 위해 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);
}
}
이 수정이 없으면 코드는 배열의 시작 부분에 요소를 삽입 할 수 없습니다.
답변
나는 이것이 이미 답을 가지고있는 오래된 질문이라는 것을 알고 있으며, 다른 괜찮은 대답이 많이 있습니다. O (log n)에서 올바른 삽입 색인을 찾아서이 문제를 해결할 수 있다고 제안하는 답변이 있습니다.하지만 할 수는 있지만 배열을 부분적으로 복사해야하기 때문에 그 시간에 삽입 할 수 없습니다 우주.
결론 : 실제로 정렬 된 배열에 O (log n) 삽입 및 삭제가 필요한 경우 배열이 아닌 다른 데이터 구조가 필요합니다. B- 트리를 사용해야합니다 . 대용량 데이터 세트에 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;
}
답변
삽입 함수는 주어진 배열이 정렬되어 있다고 가정하고, 일반적으로 배열의 몇 가지 요소 만보고 새 요소를 삽입 할 수있는 위치를 직접 검색합니다.
배열의 일반적인 정렬 기능은 이러한 단축키를 사용할 수 없습니다. 분명히 배열의 모든 요소를 검사하여 이미 올바르게 정렬되어 있는지 확인해야합니다. 이 사실만으로도 삽입 기능보다 일반 정렬 속도가 느려집니다.
일반적인 정렬 알고리즘은 일반적으로 평균 O (n ⋅ log (n)) 이며 구현에 따라 배열이 이미 정렬 된 경우 실제로 최악의 경우 일 수 있으며 O (n 2 )의 복잡성을 초래 합니다. 삽입 위치를 직접 검색하는 대신 O (log (n)) 의 복잡성이 있으므로 항상 훨씬 빠릅니다.
답변
소수의 항목의 경우 그 차이는 매우 사소합니다. 그러나 많은 항목을 삽입하거나 매우 큰 배열을 사용하는 경우 삽입 할 때마다 .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) 사용자 정의 비교기 기능을 받아들이지 않고 비교할 가치를 얻는 방법 만 (기본 비교기를 사용하여 가정합니다).