Insert an item into sorted list in Python
Use the insort function of the bisect module:
import bisect a = [1, 2, 4, 5] bisect.insort(a, 3) print(a) Solution 2
Hint 1: You might want to study the Python code in the bisect module.
Hint 2: Slicing can be used for list insertion:
>>> s = ['a', 'b', 'd', 'e'] >>> s[2:2] = ['c'] >>> s ['a', 'b', 'c', 'd', 'e'] Solution 3
You should use the bisect module. Also, the list needs to be sorted before using bisect.insort_left
It’s a pretty big difference.
>>> l = [0, 2, 4, 5, 9] >>> bisect.insort_left(l,8) >>> l [0, 2, 4, 5, 8, 9] timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000) 1.2235019207000732 timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000) 0.041441917419433594 Solution 4
I’m learning Algorithm right now, so i wonder how bisect module writes. Here is the code from bisect module about inserting an item into sorted list, which uses dichotomy:
def insort_right(a, x, lo=0, hi=None): """Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. 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) while lo < hi: mid = (lo+hi)//2 if x < a[mid]: hi = mid else: lo = mid+1 a.insert(lo, x) Solution 5
This is a possible solution for you:
a = [15, 12, 10] b = sorted(a) print b # --> b = [10, 12, 15] c = 13 for i in range(len(b)): if b[i] > c: break d = b[:i] + [c] + b[i:] print d # --> d = [10, 12, 13, 15] Insert an item into sorted list in Python
This is the best way to append the list and insert values to sorted list:
a = [] num = int(input('How many numbers: ')) for n in range(num): numbers = int(input('Enter values:')) a.append(numbers) b = sorted(a) print(b) c = int(input("enter value:")) for i in range(len(b)): if b[i] > c: index = i break d = b[:i] + [c] + b[i:] print(d)` 
Veera Pathiran 1
# function to insert a number in an sorted list def pstatement(value_returned): return print('new sorted list =', value_returned) def insert(input, n): print('input list = ', input) print('number to insert = ', n) print('range to iterate is =', len(input)) first = input[0] print('first element =', first) last = input[-1] print('last element =', last) if first > n: list = [n] + input[:] return pstatement(list) elif last < n: list = input[:] + [n] return pstatement(list) else: for i in range(len(input)): if input[i] >n: break list = input[:i] + [n] + input[i:] return pstatement(list) # Input values listq = [2, 4, 5] n = 1 insert(listq, n) Some more answer related to the same question
Well there are many ways to do this, here is a simple naive program to do the same using inbuilt Python function sorted()
def sorted_inserter(): list_in = [] n1 = int(input("How many items in the list : ")) for i in range (n1): e1 = int(input("Enter numbers in list : ")) list_in.append(e1) print("The input list is : ",list_in) print("Any more items to be inserted ?") n2 = int(input("How many more numbers to be added ? : ")) for j in range (n2): e2= int(input("Add more numbers : ")) list_in.append(e2) list_sorted=sorted(list_in) print("The sorted list is: ",list_sorted) sorted_inserter() How many items in the list : 4
Enter numbers in list : 123
Enter numbers in list : 523
The input list is : [1, 2, 123, 523]
Any more items to be inserted ?
How many more numbers to be added ? : 1
The sorted list is: [1, 2, 9, 123, 523]
This is a possible solution for you:
a = [15, 12, 10] b = sorted(a) print b # --> b = [10, 12, 15] c = 13 for i in range(len(b)): if b[i] > c: break d = b[:i] + [c] + b[i:] print d # --> d = [10, 12, 13, 15] Related question
If there are no artificial restrictions, bisect.insort() should be used as described by stanga . However, as Velda mentioned in a comment, most real-world problems go beyond sorting pure numbers.
Fortunately, as commented by drakenation , the solution applies to any comparable objects. For example, bisect.insort() also works with a custom dataclass that implements __lt__() :
from bisect import insort @dataclass class Person: first_name: str last_name: str age: int def __lt__(self, other): return self.age < other.age persons = [] insort(persons, Person('John', 'Doe', 30)) insort(persons, Person('Jane', 'Doe', 28)) insort(persons, Person('Santa', 'Claus', 1750)) # [Person(first_name='Jane', last_name='Doe', age=28), Person(first_name='John', last_name='Doe', age=30), Person(first_name='Santa', last_name='Claus', age=1750)] However, in the case of tuples, it would be desirable to sort by an arbitrary key. By default, tuples are sorted by their first item (first name), then by the next item (last name), and so on.
As a solution you can manage an additional list of keys:
from bisect import bisect persons = [] ages = [] def insert_person(person): age = person[2] i = bisect(ages, age) persons.insert(i, person) ages.insert(i, age) insert_person(('John', 'Doe', 30)) insert_person(('Jane', 'Doe', 28)) insert_person(('Santa', 'Claus', 1750)) Official solution: The documentation of bisect.insort() refers to a recipe how to use the function to implement this functionality in a custom class SortedCollection , so that it can be used as follows:
>>> s = SortedCollection(key=itemgetter(2)) >>> for record in [ . ('roger', 'young', 30), . ('angela', 'jones', 28), . ('bill', 'smith', 22), . ('david', 'thomas', 32)]: . s.insert(record) >>> pprint(list(s)) # show records sorted by age [('bill', 'smith', 22), ('angela', 'jones', 28), ('roger', 'young', 30), ('david', 'thomas', 32)] Following is the relevant extract of the class required to make the example work. Basically, the SortedCollection manages an additional list of keys in parallel to the items list to find out where to insert the new tuple (and its key).
from bisect import bisect_left class SortedCollection(object): def __init__(self, iterable=(), key=None): self._given_key = key key = (lambda x: x) if key is None else key decorated = sorted((key(item), item) for item in iterable) self._keys = [k for k, item in decorated] self._items = [item for k, item in decorated] self._key = key def __getitem__(self, i): return self._items[i] def __iter__(self): return iter(self._items) def insert(self, item): 'Insert a new item. If equal keys are found, add to the left' k = self._key(item) i = bisect_left(self._keys, k) self._keys.insert(i, k) self._items.insert(i, item) Note that list.insert() as well as bisect.insort() have O(n) complexity. Thus, as commented by nz_21 , manually iterating through the sorted list, looking for the right position, would be just as good in terms of complexity. In fact, simply sorting the array after inserting a new value will probably be fine, too, since Python's Timsort has a worst-case complexity of O(n log(n)). For completeness, however, note that a binary search tree (BST) would allow insertions in O(log(n)) time.
Tobias Uhmann 2387
I'm learning Algorithm right now, so i wonder how bisect module writes. Here is the code from bisect module about inserting an item into sorted list, which uses dichotomy:
def insort_right(a, x, lo=0, hi=None): """Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. 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) while lo < hi: mid = (lo+hi)//2 if x < a[mid]: hi = mid else: lo = mid+1 a.insert(lo, x) 
请叫我小马哥 1523
You should use the bisect module. Also, the list needs to be sorted before using bisect.insort_left
It's a pretty big difference.
>>> l = [0, 2, 4, 5, 9] >>> bisect.insort_left(l,8) >>> l [0, 2, 4, 5, 8, 9] timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000) 1.2235019207000732 timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000) 0.041441917419433594 Hint 1: You might want to study the Python code in the bisect module.
Hint 2: Slicing can be used for list insertion:
>>> s = ['a', 'b', 'd', 'e'] >>> s[2:2] = ['c'] >>> s ['a', 'b', 'c', 'd', 'e'] Use the insort function of the bisect module:
import bisect a = [1, 2, 4, 5] bisect.insort(a, 3) print(a) Related Query
- python dictionary put values of keys into a list where the keys are in another list
- How to convert list into string without loop and join() in Python
- How to convert a strictly sorted list of strings into dict?
- Insert a Node at the Tail of a Linked List python HackerRank
- Split Python list of strings into seperate lists based on character
- Python MySQLdb select from and insert into another database
- Splitting a url into a list in python
- Splitting a string into a list in python
- python - Splitting a list of integers into list of digits
- How to insert elements of a list into another list depending on date value?
- Insert a row in to google BigQuery table from the values of a python list
- Setting the list item in a Python for loop
- Get a slice of a sorted list according to a key in Python
- Insert multiple list items into another list
- how to check item in a list contains in python
- How to turn a python dictionary into a list with intentionally duplicate values
- How to insert a picture into Excel at a specified cell position with python (Anaconda) use vba
- How to Reorder Python List For Every N Item
- python convert string of lists into a list of lists
- python 2.7.5+ split list ['a', 'yyy yyy zzz'] into list ['a', 'yyy', 'yyy', 'zzz'] how?
- Python finding minimum values of functions of list items, but returning the list item
- Python cannot copy item to list
- How key in python sorted method can use a list
- Concatenate list elements into string in python
- Python - split a list of dicts into individual dicts
- Split list into two parts based on some delimiter in each list element in python
- transforming a string into a list in python
- Convert list into tuple then add this tuple into list in python
- python count list item occurences and put result in list
- Convert Python list of strings into floats, where list also contains words
More Query from same tag
- python remove element containing namespace
- pop() function not functioning right in a for loop
- Twisted Error: Request.write called on a request after Request.finish was called
- Inspect stack of traits for TreeView?
- Implementing forward declarations for functions in Python
- How to use Scrapy to collect data from different parts in a page?
- How to plot a stacked bar chart using hvplot?
- Parsing strange web page - multiple html tags
- How to append and prepend HTML substrings into a matched string using regular expression in python?
- How can I represent an array of bytes in Python?
- python selenium element not visible
- Can one define functions like in JavaScript?
- sys.exit() Is not killing process
- Using zip and list comprehension to create a dictionary
- Main menu help (pygame)
- Elasticsearch update document in python
- Python: Reading files in binary mode does not return expected values
- How does the tensorflow session.run() method knows the name of the placeholder variables?
- How can I efficiently compute the md5 sum of an iterable of bits in Python?
- Python Subclasses Seemingly Editing Eachother
- Objects having same name refer to different id in python
- the meaning of * (zero time or many times) in the python regular expression
- Bokeh bar chart does not show correctly
- How can I insert in the middle of a multilayered nested list?
- Efficiently identifying ancestors/descendants within a given distance, in networkx
- Hexadecimal convertion error in python
- Chord Diagram in Python
- How can I read .txt file from S3 bucket using python and view the contents?
- Seaborn histogram with 4 panels (2 x 2) in Python
- Create text mask using Python+PIL or Imagemagick
- or condition in while loop python
- exit(1) in signal handler just gets caught as SystemExit as there is nothing to it
- Python C-API: Using `PySequence_Length` with dictionaries
- Python Optimization using gekko
- creating and using a preferences file in python