Introduction
This module bisect
provides support for maintaining a list in sorted
order without having to sort the list after each insertion.
For long lists of items with expensive comparison operations,
this can be an improvement over linear searches or frequent
resorting.
Project #1
Create an interactive program to allow the user to
demonstrate various bisect functions. The program should
allow the user to:
- crate an initial list of to work with
- select which function to demonstrate
bisect(), bisect_left(),
bisect_right(),insort(),isort_left(),isort_right()
- enter an insertion commands
- insertion value
- insertion lo and hi (optional)
- display the before and after results
Note: To simplify things, the program should use only integers.
Project #2
Use keys. Demonstrate keys using a different program?
The data is a list of tuples?
links
bisect — Array bisection algorithm
(Python Documentation)
Bisect Algorithm Functions in Python
Python Bisect Module | Usage Guide (With Examples)
Speed comparison between bisect.insort function and list.index and insert function
Code Example
#=============================================================
# www.geeksforgeeks.org/bisect-algorithm-functions-in-python/
# Python code to demonstrate the working of
# insort(), insort_left() and insort_right()
# ============================================================
import bisect
# initializing list
li1 = [1, 3, 4, 4, 4, 6, 7]
# initializing list
li2 = [1, 3, 4, 4, 4, 6, 7]
# initializing list
li3 = [1, 3, 4, 4, 4, 6, 7]
# initializing list
li4 = []
# ---- using insort() to insert 5 at appropriate position
print()
print ("Inserting new element using insort()")
print(f'initial list: id={id(li1)} {li1}')
# using insort() to insert 5 at appropriate position
print('insert 5')
bisect.insort(li1, 5)
print(f'final list : id={id(li1)} {li1}')
# ---- using insort_left() to insert 5 at appropriate position
print()
print ("Inserting new element using insort_left()")
print(f'initial list: id={id(li2)} {li2}')
# using insort() to insert 5 at appropriate position
print('insert_left 5')
bisect.insort_left(li2, 5)
print(f'final list : id={id(li2)} {li2}')
# ---- using insort_right() to insert 5 at appropriate position
print()
print ("Inserting new element using insort_right()")
print(f'initial list: id={id(li3)} {li3}')
print('insert_right 5, 0, 4')
bisect.insort_right(li3, 5, 0, 4)
print(f'final list : id={id(li3)} {li3}')
# ---- using insort() to insert several numbers at
# ---- appropriate positions
print()
print ("Inserting new elements using insort()")
print(f'initial list: id={id(li4)} {li4}')
for i in [5,2,7,8,10,8,1,0]:
print(f'insert {i}')
bisect.insort(li4,i)
print(f'final list : id={id(li4)} {li4}')