Insérer un élément dans une liste triée en Python

Question

Je crée une classe où l'une des méthodes insère un nouvel élément dans la liste triée. L'élément est inséré à la position corrigée (triée) dans la liste triée. Je ne suis pas autorisé à utiliser des fonctions ou méthodes de liste intégrées autres que [] , [:] , + et len . C'est la partie qui est vraiment déroutante pour moi.

Quelle serait la meilleure façon de procéder?

Answer 1

Utilisez la fonction insort du module bisect :

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

Production

 [1, 2, 3, 4, 5] 

Answer 2

Astuce 1 : Vous voudrez peut-être étudier le code Python dans le module bisect .

Astuce 2 : le découpage peut être utilisé pour l'insertion de liste :

 >>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']

Answer 3

Vous devez utiliser le module bisect. De plus, la liste doit être triée avant d'utiliser bisect.insort_left

C'est une assez grosse différence.

 >>> 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 4

J'apprends l'algorithme en ce moment, alors je me demande comment le module bisect écrit. Voici le code du module bisect sur l'insertion d'un élément dans une liste triée, qui utilise la dichotomie :

 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 5

Voici une solution possible pour vous :

 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]