Insert an item into sorted list in Python

Question

I'm creating a class where one of the methods inserts a new item into the sorted list. The item is inserted in the corrected (sorted) position in the sorted list. I'm not allowed to use any built-in list functions or methods other than [], [:], +, and len though. This is the part that's really confusing to me.

What would be the best way in going about this?

Answer 1

Starting from Python 3.10: When you want to insert an element into a list of tuples where the first element is comparable and the second is not you can use the key parameter of the bisect.insort function as follows:

import bisect 

class B:
    pass

a = [(1, B()), (2, B()), (3, B())] 
bisect.insort(a, (3, B()), key=lambda x: x[0]) 
print(a)

Without the lambda function as the third parameter of the bisect.insort function the code would throw a TypeError as the function would try to compare the second element of a tuple as a tie breaker which isn't comparable by default.

Answer 2

Use the insort function of the bisect module:

import bisect 
a = [1, 2, 4, 5] 
bisect.insort(a, 3) 
print(a)

Output

[1, 2, 3, 4, 5] 

For more complicated usage, check key parameter for insort method

import bisect
a = [{"key": 1}, {"key": 3}]
bisect.insort(a, {"key": 2}, key=lambda x: x["key"])
print(a)

Output

[{"key": 1}, {"key": 2}, {"key": 3}]

Answer 3

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.

Answer 4

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()

The output is

How many items in the list : 4

Enter numbers in list : 1

Enter numbers in list : 2

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

Add more numbers : 9

The sorted list is: [1, 2, 9, 123, 523]

Answer 5

# 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)

Answer 6

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)

Answer 7

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]

Answer 8

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)`

Answer 9

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

Answer 10

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']