Interclasarea din merge sort pierde elementele rămase dintr-una dintre liste
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
while i < len(a) and j < len(b):
...
return rezwhile i < len(a) and j < len(b):
...
rez.extend(a[i:])
rez.extend(b[j:])
return rezCel 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ă
rez.extend(a[i:])
return rezrez.extend(a[i:])
rez.extend(b[j:])
return rezNu știi dinainte care listă se termină prima, deci adaugi restul din ambele.
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].
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)[1, 2, 3, 4, 9]
Indiciu
După buclă, una dintre liste mai are elemente: adaugă-le la rezultat.
Reparația
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
rez.extend(a[i:])
rez.extend(b[j:])
return rez
rez = interclaseaza([1, 4, 9], [2, 3])
assert rez == [1, 2, 3, 4, 9], f'elemente lipsa: {rez}'
print(rez)De ce merge
După ce 2 și 3 au fost puse în rezultat, lista b s-a terminat, iar bucla s-a oprit cu i = 2, deci 9 a rămas neadăugat. rez.extend(a[i:]) adaugă [9], iar rez.extend(b[j:]) adaugă o listă goală. Pentru că restul provine dintr-o listă sortată și e mai mare decât tot ce s-a pus deja, rezultatul rămâne sortat.
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
RecursionError în merge sort: cazul de bază nu oprește lista cu un element Cazul de bază din merge sort verifică doar lista goală (if not lista), dar o listă cu un element se împarte în [] și [x], iar [x] se reîmparte la nesfârșit. Oprește recursivitatea la cel mult un element: if len(lista) <= 1: return lista. IndexError: list index out of range la două pointere Pointerul din dreapta a pornit de la len(lista) în loc de len(lista) - 1, sau unul din pointeri a ieșit din listă fără ca bucla să se oprească. Pornește cu dreapta = len(lista) - 1 și pune condiția stanga < dreapta în while. RecursionError în quicksort: pivotul rămâne în sublista din stânga Sublista cu elementele mai mici sau egale conține și pivotul, deci când pivotul e maximul, apelul recursiv primește aceeași listă la nesfârșit. Scoate pivotul înainte de împărțire (lista[1:]) și pune-l separat între cele două părți. Î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.
