SortedArray

!CI workflow

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

``bash
npm install @fgiova/sorted-array
`

Usage

`typescript
import { SortedArray } from "@fgiova/sorted-array";

const array = new SortedArray();

array.push(1, 3);
array.insert(2);

console.log(array); // [1, 2, 3]
`

$3


`typescript
new SortedArray(items?: T[] comparator?: (a: T, b: T) => number);
`
default comparator is:
`typescript
function comparatorFunction(a, b) {
if (a < b) return -1;
if (a >= b) return 1;
return 0;
}
`

$3

- splice
- sort
- reverse
- copyWithin
- fill

$3

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% |