...
Eroare Algoritmi și structuri de date · Căutare binară și sortări

IndexError: list index out of range la sortarea prin inserție (lipsește j >= 0)

Pe scurt

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

Greșit
PYTHON
while nums[j] > x:
    nums[j + 1] = nums[j]
    j -= 1
Corect
PYTHON
while j >= 0 and nums[j] > x:
    nums[j + 1] = nums[j]
    j -= 1

Câ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ă

Greșit
PYTHON
while nums[j] > x and j >= 0:
Corect
PYTHON
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ă tu

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]).

Codul care dă eroarea
PYTHON
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]))
După reparație, programul afișează
[1, 2, 3]
[1, 2, 4, 5, 9]
Indiciu

Bucla interioară trebuie să se oprească și când j ajunge înaintea primului element.

Alte forme ale mesajului

  • IndexError: list index out of range
  • IndexError: 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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.