@fgiova/sorted-array
v1.0.0
Published
permanent sorted array
Downloads
3
Readme
SortedArray
Description
This simple module provides an array implementation, with a sorting feature using binary search algorithm.
Each time an element is inserted, it is placed in the correct position, so that the array is always sorted. The sorting is implemented using binary search algorithm, so the complexity is O(log n). All the elements are compared using the comparator function assigned on constructor or by default sort function. The array as implemented using a native array, so it is not a linked list. The array is mutable, but you cannot change the length of the array or remove elements except from the starting or ending array. Methods that change the sort order are not implemented; the array is always sorted according to the default order of the comparison function.
Installation
npm install @fgiova/sorted-array
Usage
import { SortedArray } from "@fgiova/sorted-array";
const array = new SortedArray<number>();
array.push(1, 3);
array.insert(2);
console.log(array); // [1, 2, 3]
Constructor
new SortedArray<T>(items?: T[] comparator?: (a: T, b: T) => number);
default comparator is:
function comparatorFunction(a, b) {
if (a < b) return -1;
if (a >= b) return 1;
return 0;
}
Not implemented methods
splice
sort
reverse
copyWithin
fill
Benchmark
I have made a simple benchmark using Benchmark.js, comparing the performance of the push
+ sort
methods of the native array and the insert
method of this module.
The benchmark is available in the benchmark
folder.
The results are the following:
| Function | | | |-------------------|----------------|-----------| | Simple Sort Array | 228 ops/sec | ±91.75% | | Sorted Array | 3,340 ops/sec | ±46.99% |