bisec:Maintain Lists in Sorted Order
The bisec
Inserting in Sorted Order
Here is a simple example in which insort
The following codes:
import bisect
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]
print('Before ordered：', values)
print('New Pos Contents')
print('--- --- --------')
l = []
def get_order_lst(lst):
for i in lst:
position = bisect.bisect(l, i)
bisect.insort(l, i)
print('{:3} {:3} '.format(i, position), l)
return l
get_order_lst(values)
print('\nAfter ordered：', l)
The first column of the output shows the new random number. The second column shows the position where the number will be inserted into the list. The remainder of each line is the current sorted list.
Before ordered： [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]
New Pos Contents
--- --- --------
14 0 [14]
85 1 [14, 85]
77 1 [14, 77, 85]
26 1 [14, 26, 77, 85]
50 2 [14, 26, 50, 77, 85]
45 2 [14, 26, 45, 50, 77, 85]
66 4 [14, 26, 45, 50, 66, 77, 85]
79 6 [14, 26, 45, 50, 66, 77, 79, 85]
10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
77 8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
1 0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
After ordered： [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
This is a simple example. In fact, given the amount of data being manipulated, it might be faster to simply build the list and then sort it once. By contrast, for long lists, significant time and memory savings can be achieved using an insertion sort algorithm such as this, especially when the operation to compare two members of the list requires expensive computation.
