IndexError: list index out of range la sortarea prin inserție (lipsește j >= 0)
Bucla while nums[j] > x nu se oprește când j trece de începutul listei: j devine -1, -2..., Python citește elementele de la capăt și în final iese din listă. Adaugă condiția j >= 0 înaintea comparației: while j >= 0 and nums[j] > x.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Sortarea prin inserție ia fiecare element x și îl mută spre stânga cât timp elementul din fața lui e mai mare. Bucla interioară trebuie să se oprească din două motive: a găsit un element mai mic sau a ajuns la începutul listei.
Dacă uiți a doua condiție, j coboară sub 0. În Python indicii negativi nu dau eroare imediat: nums[-1] e ultimul element, nums[-2] penultimul. Bucla continuă deci să compare și să mute elemente de la capătul listei, stricând lista, până când j ajunge la -len(nums) - 1 și primești IndexError: list index out of range. Uneori, dacă un element de la capăt e mai mic, bucla se oprește înainte de eroare, iar rezultatul e doar greșit.
Ordinea condițiilor contează: j >= 0 se scrie primul, ca and să nu mai evalueze nums[j] când j a ieșit din listă.
De ce apare: cauzele frecvente
1Lipsește oprirea la începutul listei
while nums[j] > x:
nums[j + 1] = nums[j]
j -= 1while j >= 0 and nums[j] > x:
nums[j + 1] = nums[j]
j -= 1Când elementul curent e cel mai mic de până acum, el trebuie dus pe poziția 0, iar bucla se oprește la j = -1 datorită primei condiții.
2Condițiile în ordine inversă
while nums[j] > x and j >= 0:while j >= 0 and nums[j] > x:and evaluează de la stânga la dreapta. Cu verificarea indicelui prima, nums[j] nu se mai citește pentru j negativ.
Repară eroarea, direct în pagină
Funcția sortare_insertie(nums) dă IndexError: list index out of range pentru lista [3, 1, 2]. Repar-o ca să afișeze [1, 2, 3] și [1, 2, 4, 5, 9] (pentru [5, 2, 9, 1, 4]).
def sortare_insertie(nums):
for i in range(1, len(nums)):
x = nums[i]
j = i - 1
while nums[j] > x:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = x
return nums
print(sortare_insertie([3, 1, 2]))
print(sortare_insertie([5, 2, 9, 1, 4]))[1, 2, 3] [1, 2, 4, 5, 9]
Indiciu
Bucla interioară trebuie să se oprească și când j ajunge înaintea primului element.
Reparația
def sortare_insertie(nums):
for i in range(1, len(nums)):
x = nums[i]
j = i - 1
while j >= 0 and nums[j] > x:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = x
return nums
print(sortare_insertie([3, 1, 2]))
print(sortare_insertie([5, 2, 9, 1, 4]))De ce merge
Pentru x = 1, bucla muta 3 la dreapta și ajungea la j = -1. Fără verificare, nums[-1] (ultimul element) era comparat și mutat, apoi nums[-2] și tot așa, până când indicele ieșea din listă. Cu j >= 0 pus primul, bucla se oprește când a mutat toate elementele mai mari, iar nums[j + 1] = x pune 1 pe poziția 0.
Alte forme ale mesajului
IndexError: list index out of rangeIndexError: list assignment index out of range
Cum o eviți pe viitor
În orice buclă care mută un indice spre stânga (inserție, două pointere, parcurgere inversă), scrie întâi condiția de margine (j >= 0) și abia apoi comparația cu valoarea. Testează sortarea pe o listă în care cel mai mic element e la final, de exemplu [3, 1, 2] sau [5, 4, 3, 2, 1]: acolo elementul trebuie dus până la poziția 0.
Întrebări frecvente
De ce nu primesc eroarea imediat la j = -1?
Pentru că nums[-1] e un indice valid în Python: ultimul element. Eroarea apare abia când indicele negativ depășește lungimea listei, după ce lista a fost deja amestecată.
Merită să scriu sortarea prin inserție în cod real?
Nu, sorted și list.sort sunt mai rapide și corecte. Sortarea prin inserție e utilă la învățare și pe liste aproape sortate, unde face aproape O(n) pași.
Erori înrudite
IndexError: list index out of range la lista[i + 1] Compari fiecare element cu următorul (lista[i] și lista[i + 1]), dar bucla merge până la ultimul element, care nu are un următor. Oprește bucla cu un pas mai devreme: for i in range(len(lista) - 1). Bucla inversă range(len(nums) - 1, 0, -1) sare peste primul element range se oprește înainte de valoarea stop, deci range(n - 1, 0, -1) se termină la 1 și nu ajunge la indexul 0. Pentru a parcurge toți indicii de la coadă scrie range(len(nums) - 1, -1, -1) sau reversed(range(len(nums))). Vecinul grila[-1][j] nu dă eroare: indicii negativi trec de verificarea marginii În Python, grila[-1] e ultimul rând, nu o eroare. Dacă verifici doar i < len(grila), vecinul de deasupra primului rând „există” și BFS/DFS-ul trece pe partea cealaltă a hărții. Verifică ambele margini: 0 <= i < randuri and 0 <= j < coloane. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
