ソートされた JavaScript 配列があり、結果の配列がソートされたままになるように配列にもう 1 つの項目を挿入したいと考えています。簡単なクイックソート スタイルの挿入関数を実装することは可能です。
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));
2 番目の実装よりも最初の実装を選択する正当な理由はありますか?
編集: 一般的なケースでは、O(log(n)) 挿入 (最初の例で実装されている) は一般的なソート アルゴリズムよりも高速になりますが、これは必ずしも JavaScript に当てはまるとは限りません。次の点に注意してください。
- いくつかの挿入アルゴリズムの最良のケースはO(n)ですが、これはO(log(n))とは大きく異なりますが、後述するようにO(n log(n))ほど悪くはありません。これは、使用される特定のソートアルゴリズムに依存します（Javascript Array.sort の実装?）
- JavaScript の sort メソッドはネイティブ関数であるため、潜在的に大きなメリットが実現されますが、大きな係数を持つ O(log(n)) は、適度なサイズのデータ セットの場合、O(n) よりもはるかに悪くなる可能性があります。
ベストアンサー1
単純 （デモ):
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;
}