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

Interclasarea din merge sort pierde elementele rămase dintr-una dintre liste

Pe scurt

Bucla while i < len(a) and j < len(b) se oprește când una dintre liste se termină, iar elementele rămase din cealaltă nu mai ajung în rezultat. După buclă adaugă restul: rez.extend(a[i:]) și rez.extend(b[j:]).

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Interclasarea combină două liste sortate într-una singură: compari primele elemente rămase și îl iei pe cel mai mic. Bucla principală merge cât timp ambele liste mai au elemente, pentru că altfel nu ai ce compara.

Când una dintre liste s-a terminat, în cealaltă pot rămâne mai multe elemente, toate mai mari decât ce ai pus deja. Dacă nu le adaugi după buclă, ele se pierd. Rezultatul e mai scurt decât suma lungimilor, iar merge sort-ul construit pe această funcție returnează liste cu elemente lipsă.

Nu primești nicio eroare. Semnul cel mai simplu: len(rez) != len(a) + len(b). Merită să pui un assert exact pe asta când scrii interclasarea prima dată.

De ce apare: cauzele frecvente

1Lipsește adăugarea restului

Greșit
PYTHON
while i < len(a) and j < len(b):
    ...
return rez
Corect
PYTHON
while i < len(a) and j < len(b):
    ...
rez.extend(a[i:])
rez.extend(b[j:])
return rez

Cel puțin una dintre feliile a[i:] și b[j:] e goală, iar cealaltă conține exact elementele rămase, deja sortate.

2Ai adăugat doar restul dintr-o listă

Greșit
PYTHON
rez.extend(a[i:])
return rez
Corect
PYTHON
rez.extend(a[i:])
rez.extend(b[j:])
return rez

Nu știi dinainte care listă se termină prima, deci adaugi restul din ambele.

Repară tu

Repară eroarea, direct în pagină

Funcția interclaseaza(a, b) combină două liste sortate. Testul cu assert pică: din rezultat lipsește valoarea 9. Repar-o ca să afișeze [1, 2, 3, 4, 9] pentru [1, 4, 9] și [2, 3].

Codul care dă eroarea
PYTHON
def interclaseaza(a, b):
    rez = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            rez.append(a[i])
            i += 1
        else:
            rez.append(b[j])
            j += 1
    return rez

rez = interclaseaza([1, 4, 9], [2, 3])
assert rez == [1, 2, 3, 4, 9], f'elemente lipsa: {rez}'
print(rez)
După reparație, programul afișează
[1, 2, 3, 4, 9]
Indiciu

După buclă, una dintre liste mai are elemente: adaugă-le la rezultat.

Cum o eviți pe viitor

După orice buclă cu două pointere care se oprește când unul dintre ele ajunge la capăt, întreabă-te ce s-a întâmplat cu elementele de la celălalt. Scrie un test în care o listă se termină mult mai devreme ([1, 4, 9] cu [2, 3]) și verifică lungimea rezultatului. În cod real, heapq.merge(a, b) sau sorted(a + b) fac același lucru fără risc.

Întrebări frecvente

Elementele rămase trebuie comparate între ele?

Nu. Ele provin dintr-o listă sortată și sunt toate mai mari sau egale cu ultimul element pus în rezultat, deci le poți adăuga direct, în ordine.

De ce folosesc <= și nu < la comparație?

Cu <=, la valori egale iei întâi elementul din prima listă, deci sortarea rămâne stabilă: elementele egale își păstrează ordinea inițială.

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.