Insert number in a sorted list of tuples based on their 3rd number

Question

Suppose I have a list A and when I insert tuple B, I get list C. List A is a sorted list based on the 3rd number of each tuple

In short: How do I insert this tuple into list A while keeping the list sorted based on the 3rd value.

INSERT TO NOT SORT this is not the same question as this one How to sort a list/tuple of lists/tuples by the element at a given index?

because sorting the list is simply too slow.

A = [(1, 2, 1),(1, 2, 2),(1, 2, 3),(1, 2, 5)]

insert --> B: (1, 2, 4)

C = [(1, 2, 1),(1, 2, 2),(1, 2, 3),(1, 2, 4),(1, 2, 5)]

Oh. Well, there's https://stackoverflow.com/questions/27672494/how-to-use-bisect-insort-left-with-a-key. Unfortunately, the standard library doesn't build in support for this. Keep in mind, though, that inserting into a `list` is O(N) even if you can find the insertion point faster than that. Iteratively building the list this way will be O(N^2), while putting in everything at once and sorting once is O(N lg N). If you need to do repeated updates efficiently, you want a different data structure, one that you'll have to either create yourself or get from a third-party library. — Karl Knechtel, Sep 05 '21 at 20:39
Also, if you do want to insert into the sorted position and not do "add at the end" + "sort after" method, then implement a [Binary Tree](https://stackoverflow.com/a/28864021/1431750) where the `val` is your tuple. Or store the tuple as the val and maintain a separate "key" which is always assigned the 3rd item of the tuple. However, you'd need to implement your own `to_list()` method (or override `__iter__` and do `list(tree)`) to get a list-version of the tree. Why is sorting it slow? Why is insert + sort repeatedly better than all inserts and one sort? Show what you have tried so far (code) — aneroid, Sep 06 '21 at 12:58

Gábor Pálovics · Accepted Answer · 2021-09-06T19:02:17.450

The efficient way would be to use something similar to bisect. Unfortunately, I believe it's not doable with the original implementation of the package, but this version supports the key parameter: https://github.com/python/cpython/blob/main/Lib/bisect.py

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

Then you can simply call

C = A.copy()
C.insert(bisect_left(A, B, key=lambda tup: tup[2]), B)

Insert number in a sorted list of tuples based on their 3rd number

1 Answers1