python bisect.insort(list, value)

Question

does this python module computes an ordered insert into a data structure or it inserts and then sort? been struggling with this kind of thing in python since developing an algorithm in which I have to keep in mind memmory issues thus need a way to insert into a list just in the right position, as it should be done in java using a linkedlist but not sure what to use and how.

Any help will be much appreciated.

Solution

This insert value in a list at the correct position, note that it assumes is already sorted. From the documentation:

Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

The last part refers to the fact that insertion on a Python list is O(n). The search is done using binary search.

If you start from an empty list and repeatedly use this algorithm to insert the objects into a list, the final list will be sorted. This algorithm is known as binary insertion sort. For example:

import bisect

l = [1, 3, 7, 5, 6, 4, 9, 8, 2]

result = []
for e in l:
    bisect.insort(result, e)

print(result)

Output

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Note: The complexity of this algorithm is O(n*n) given the O(n) insertion step.

Comments

[jupcan]

so if i have kind of a frontier and want to insert objects of another class in the correct position depending on a random attribute that is generated, does this module help me out to insert it in the correct position? at the beggining the list is empty so if using this i guess it will always insert in the correct way without actually sorting the list but not sure do :/ that's why im asking for advice, ty.

[Dani Mesejo]

@jupcan Basically yes, the array will remain sorted. I updated the answer.

[jupcan]

thank u very much! and there is no better way to do smth similar right?

[Dani Mesejo]

@jupcan you could insert at the end using append (the method from list) and then sort the list using as key your attribute.

[jupcan]

but the complexity of that would be greater wouldn't it? have tried before and the time it takes for large amount of data grows exponentially