Insert an Item into Sorted List in Python

Python: insert new element into sorted list of dictionaries

Since a insertion in a list is in O(n) anyway, any clever bisect algorithm is not that useful, so you can simply loop the list to find the position where it should be inserted, and then insert it. Something like:

new_value = {'id': 6, 'name': 'Jenkins'}

for index, value in enumerate(y):
    # Assuming y is in increasing order.
    if value['id'] > new_value['id']:
        y.insert(index, new_value)
        break

Insert a custom object in a sorted list

You can do this for your custom object if you implement the __lt__ method, because this is what bisect will use to compare your object.

>>> class Foo(object):
...     def __init__(self, val):
...         self.prop = val # The value to compare
...     def __lt__(self, other):
...         return self.prop < other.prop
...     def __repr__(self):
...         return 'Foo({})'.format(self.prop)
...
>>> sorted_foos = sorted([Foo(7), Foo(1), Foo(3), Foo(9)])
>>> sorted_foos
[Foo(1), Foo(3), Foo(7), Foo(9)]
>>> bisect.insort_left(sorted_foos, Foo(2))
>>> sorted_foos
[Foo(1), Foo(2), Foo(3), Foo(7), Foo(9)]

Python sorted list insertion

def insert(a, tab):
    l = list(tab)
    l.append(a)
    i = len(l) - 2
    while a < l[i] and i >= 0:
        l[i+1] = l[i]
        l[i] = a
        i -= 1
    return l

Insert item into case-insensitive sorted list in Python

It's a good opportunity to practice binary search again (or just copy&paste&modify bisect.insort, which is what I did):

def insort_case_insensitive(a, x):
    key = x.lower()
    lo, hi = 0, len(myList)
    while lo < hi:
        mid = (lo + hi) // 2
        if key < a[mid].lower():
            hi = mid
        else:
            lo = mid + 1
    a.insert(lo, x)

Demo:

myList = ['a', 'b', 'c', 'd', 'e']
for x in 'A', 'B', 'C', 'D', 'E':
    insort_case_insensitive(myList, x)
print myList

Prints:

['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E']

It's O(n), just like append+sort would be, but only because of the a.insert(lo, x) at the end. Which is dead-simple and done in C, so it's super fast. The binary search of course only takes O(log n) steps, so that's super fast as well. The append+sort way would call .lower() on all elements and compare them, both of which is much slower. @MoinuddinQuadri's first solution is also much slower because of calling .lower() on all elements.

See my other answer for a benchmarking comparison.

fastest way to find insert position for new data into sorted list of dates

In general, the best you can do to find the location is a logarithmic search. But the details depends on what you have.

Also, notice that even if you improve the search from linear time to logarithmic, if you're using a data structure like a list or array, the insert is still going to take linear time (because it has to shift the rest of the list up). So you may be optimizing the wrong thing.

• For a very small collection, like a list of 5 values, you're probably better off just using linear search.
• If you're doing almost all of your inserts in one phase, and then almost all of your searches after the collection is mostly already built, just collect everything with set.add or list.append, then sort it at the end of the phase. This is still effectively (amortized) log time, but with a much better multiplier.
• For a list or other plain Sequence, use bisect from the stdlib.
• For a numpy array, or something built on top of it like a pandas Series: use numpy's searchsorted. (If you're storing a bunch of Pandas Timestamp objects, you probably should be using one of these data structures instead of a list, if you aren't already.)
• If you're doing lots of inserts (and deletes?) interleaved with lookups, you may want to switch to a logarithmic data structure. There are many options here, but something like blist is a good place to start.

How to find an index at which a new item can be inserted into sorted list and keep it sorted?

Use bisect. It's not the most beautiful API, but it's exactly what you need.

You'll want to use bisect.bisect, which returns exactly what you want.

Insert a tuple into a ordered list, according to a value in the tuple

You could use the Python bisect module.

import bisect

l = [(1, 'a'), (3, 'y'), (4, 'd')]
bisect.insort(l, (2, 'q'))

print (l)
>> [(1, 'a'), (2, 'q'), (3, 'y'), (4, 'd')]

---

Related Topics