tri par insertion dans python ne fonctionne pas

Question

I ont essayé le code suivant pour le tri par insertion dans python

a=[int(x) for x in input().split()] 
for i in range(1,len(a)): 
    temp=a[i] 
    for k in range (i,1,-1): 
     a[k]=a[k-1] 
     if a[k]<temp: 
      a[k]=temp 
      break 
print(a) 

entrée

: 6 4 3 2 5 8 1

sortie: [6, 4, 4, 4 , 4, 5, 8]

Answer 1

Il ne fonctionne pas parce que votre implémentation est défectueuse.
Lorsque vous tentez de décaler la liste partiellement triée, vous remplacez les numéros existants en affectant a[k] = a[k-1] - mais où est la précédente valeur de a[k]?

Une solution très basique (mais pas en place comme la définition d'origine sur une seule liste est définie) pourrait ressembler à ceci.

inp = '1 4 6 3 1 6 3 5 8 1' 

# 'a' is the input list 
a = [int(x) for x in inp.split()] 
# 'r' is the sorted list 
r = [] 
# In the original descriptions, insertion sort operates 
# on a single list while iterating over it. However, this 
# may lead to major failurs, thus you better carry the 
# sorted list in a separate variable if memory is not 
# a limiting factor (which it can hardly be for lists that 
# are typed in by the user). 

for e in a: 
    if not len(r): 
     # The first item is the inialization 
     r.append(e) 
    else: 
     # For each subsequent item, find the spot in 'r' 
     # where it has to go. 
     idx = 0 
     while idx < len(r) and r[idx] < e: idx += 1 
     # We are lazy and use insert() instead of manually 
     # extending the list by 1 place and copying over 
     # all subsequent items [idx:] to the right 
     r.insert(idx, e) 
print(r)