How can I push an element into array at a sorted index position?

Question

Say I have an array already with these articles, ordered by lowest to highest price:

[
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

Basically I would like to push another article into the array at the correct position (by price). How can I do so?

The new article I'm pushing may have the following properties:

{ title: "Article 5", price: 12.00 }

I'm expecting the article to appear at index 3 (between article 4 and 2).

UPDATE (SOLUTION)

I created a prototype method using @klutt's answer with binary search algorithm:

Array.prototype.pushSorted = function(el, compareFn) {
  this.splice((function(arr) {
    var m = 0;
    var n = arr.length - 1;

    while(m <= n) {
      var k = (n + m) >> 1;
      var cmp = compareFn(el, arr[k]);

      if(cmp > 0) m = k + 1;
        else if(cmp < 0) n = k - 1;
        else return k;
    }

    return -m - 1;
  })(this), 0, el);

  return this.length;
};

const sortByPrice = (a, b) => a.price > b.price;
theArray.pushSorted({ title: "Article 5", price: 12.00 }, sortByPrice);

Answer 1

Here's my current typescript implementation:

enum SortDirection {
  Ascending,
  Descending
}

const propertyComparer = <T>(
  a: T,
  b: T,
  property: keyof T,
  direction: SortDirection
): number => {
  if (a[property] < b[property]) {
    return direction === SortDirection.Ascending ? 1 : -1;
  }
  if (a[property] > b[property]) {
    return direction === SortDirection.Ascending ? -1 : 1;
  }
  return 0;
};

const findAndInsertByProperty = <T>(
  arr: T[],
  item: T,
  property: keyof T,
  direction: SortDirection
): number => {
  let start = 0;
  let end = arr.length;

  while (start < end) {
    const mid = (start + end) >> 1;
    const result = propertyComparer<T>(item, arr[mid], property, direction);

    if (result === 0) {
      return mid;
    } else if (result < 0) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }

  return end;
};

const myArray = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
];
const value = { title: "Article 5", price: 12.00 };
const valueLowest = { title: "Article 6", price: 0.49 };
const valueHighest = { title: "Article 7", price: 20.00 };

myArray.splice(findAndInsertByProperty(myArray, value, 'price', SortDirection.Descending), 0, value);
myArray.splice(findAndInsertByProperty(myArray, valueLowest, 'price', SortDirection.Descending), 0, valueLowest);
myArray.splice(findAndInsertByProperty(myArray, valueHighest, 'price', SortDirection.Descending), 0, valueHighest);

console.log(myArray);

Answer 2

I implemented this in Angular, by tweaking the code. Someone could find it useful.

Array.prototype.sortedInsert = sortedInsert;

interface Array<T> {
    sortedInsert(element: T, comparator: any): number;
}

/**
 *  This function takes an element, and a comparator function.
 *  It returns position of the inserted record.
 */

function sortedInsert<T>(element: T, comparatorFn: any): number {
    const insertionIndex: number = findInsertionIndex(this, element, comparatorFn);
    this.splice(insertionIndex, 0, element);
    return insertionIndex;
}

function findInsertionIndex<T>(arr: Array<T>, element: T, comparatorFn: any): number {
    if (arr.length === 0) {
        return 0;
    }

    let low: number = 0;
    let high: number = arr.length - 1;

    while (low <= high) {
        const mid: number = Math.floor(low + (high - low) / 2);
        const comparison: number = comparatorFn(element, arr[mid]);
        if (comparison === 0) {
            return mid;
        } else if (comparison < 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

To use this, you'll have to import this file in app.module.ts.
Usage example:

const arr = [];
const comp = (a: number, b: number) => a - b;
arr.sortedInsert(2, comp);
arr.sortedInsert(1, comp);
arr.sortedInsert(3, comp);
console.log(arr);

Answer 3

The Update (Solution) still doesn't work great. Items that should go either to the start or end get placed in the wrong position, see this revised solution based on the same code:

Array.prototype.pushSorted = function(el, compareFn) {
  let index = (function(arr) {
    var m = 0;
    var n = arr.length - 1;

    while(m <= n) {
      var k = (n + m) >> 1;
      var cmp = compareFn(el, arr[k]);

      if(cmp > 0) m = k + 1;
        else if(cmp < 0) n = k - 1;
        else {
          console.log(`m=${m} k=${k}`)
          return k;
        };
    }


    return -m - 1;
  })(this);

  if (index >= 0)
    this.splice(index, 0, el);
  else if (index < 0)
    this.splice((index * -1) - 1, 0, el);

  return this.length;
};

Sample usage:

a = [1, 2, 3, 4, 5]
a.pushSorted(2.5, (a,b) => a - b);
a.pushSorted(8, (a,b) => a - b);
a.pushSorted(0.5, (a,b) => a - b);

Answer 4

If it is a very long list, you don't want to sort the list everytime. A sorting with floats is at best O(n*log n). If you do a linear search you will have O(n) instead.

function search(a, v) {
    if(a[0]['price'] > v['price']) {
        return 0;
    }
    var i=1;
    while (i<a.length && !(a[i]['price'] > v['price'] && a[i-1]['price'] <= v['price'])) {
        i=i+1;
        }
    return i;
}

myArray.splice(search(myArray, newItem), 0, newItem)

However, if the list is VERY long it would be a good idea to do a binary search instead of a linear search. That would take it down to O(log n). A binary search is pretty simple. You start in the middle. If the element is larger than what you're searching for, apply the same algorithm to the upper half of the list, otherwise to lower part. It's easy to find code examples of binary search on the web.

Here is an example:

function binarySearch(ar, el, compare_fn) {
    if (el.price < ar[0].price)
        return 0;
    if (el.price > ar[ar.length-1].price)
        return ar.length;
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

function comp(a, b) {
    return a['price']>b['price']
}

myArray.splice(binarySearch(myArray, element, comp), 0, element)

(Stolen from here Binary Search in Javascript)

But to wrap it up. Adding the element and then sorting is usually a bad idea. Best case is that it does not matter, but since you know that the list is sorted, why not do at least a linear search?

If the lists are small, this does not matter, but if the lists have millions of elements the difference will be quite noticeable.

EDIT:

I made a quick and primitive benchmark.

            10,000   100,000  1000,000   10,000,000  
Sort            80       900     13000          N/A
Linear           2         2        25         5000
Binary           2         2         5           21

I measured the time it took to run the three algorithms on four different sizes. I did not want to wait for the sorting to end on ten million elements. Therefore the N/A. Time is in milliseconds. Note that the benchmark were very primitive, but it gives an idea about how much it affects when sizes grow.

Answer 5

To avoid sorting your array each time, you can iterate through your array until an element with greater price is found, and then use array.splice(index, 0, element) to insert your element into the correct position:

var array = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

function insertSorted (array, element, comparator) {
  for (var i = 0; i < array.length && comparator(array[i], element) < 0; i++) {}
  array.splice(i, 0, element)
}

function compareByPrice (a, b) { return a.price - b.price }

insertSorted(array, { title: "Article 5", price: 12.00 }, compareByPrice)

console.log(array)

Answer 6

Just push your item

var myArray = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

myArray.push({ title: "Article 5", price: 12.00 })

And sort you array :

myArray.sort(function(a, b) {
    return parseFloat(a.price) - parseFloat(b.price);
});

Answer 7

Consider my solution as follow;

var articles=[
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

Now write a function in this way;

function sortByKey(array, key) {
    return array.sort(function(a, b) {
        var x = a[key]; var y = b[key];
       return ((x < y) ? -1 : ((x > y) ? 1 : 0));
   });
}

Now insert an element;

articles.push({ title: "Article 5", price: 12.00 });

And finally sort it;

articles=sortByKey(articles, 'price');

Answer 8

Not sure if this is optimal, but you can push it into another (duplicated) array, then sort it, and then check for its index in order to push it at the correct index position:

Array.prototype.pushSorted = function(value, compareFunction) {
  const arrCopy = this.map(element => element);

  arrCopy.push(value);
  arrCopy.sort(compareFunction);
  this.splice(arrCopy.indexOf(value), 0, value);

  return this.length;
};

First we create a copy of the array instance. Then push the element into this array copy. Then sort the array copy. Then push (via splice method) the element into the real array while checking for its index inside the array copy. We can then return with the array length (just like a normal push).

Example:

const sortByPrice = (a, b) => a > b ? 1 : -1;
const newArticle = { title: "Article 5", price: 12.00 };

theArray.pushSorted(newArticle, sortByPrice);