De ce contează?
Imaginează-ți clasamentul unui campionat: cum ar trebui să arate la final (jucătorul 1, apoi 2, apoi 3…) și cum arată acum, după niște meciuri-surpriză. Fiecare pereche „pe dos” — un jucător slab clasat înaintea unuia mai bun — e o mică nedreptate. Numărul acelor perechi pe dos este exact numărul de inversiuni: un singur întreg care îți spune cât de amestecat e clasamentul față de cel ideal.
Intuiția
O inversiune este o pereche de poziții i mai mic decât j în care valoarea
de pe i este mai mare decât valoarea de pe j — adică două elemente care stau
în ordine greșită una față de cealaltă. Important: nu contează cât de departe sunt
cele două poziții, ci doar că prima e mai mare decât a doua.
Un vector sortat crescător are zero inversiuni; un vector sortat descrescător le
are pe toate, adică n * (n - 1) / 2 perechi. Așa că numărul de inversiuni îți
spune, printr-un singur întreg, cât de departe e vectorul de a fi sortat.
Inversiunile măsoară exact câte schimburi de vecini ar trebui să facă Bubble Sort ca să ordoneze șirul: fiecare schimb de vecini repară fix o inversiune. De aceea contorul lor apare des în probleme despre „cât de amestecat” e un șir.
Declicul rapid: la interclasarea a două jumătăți deja sortate, când iei un element din jumătatea dreaptă înaintea celor rămase în stânga, acel element formează o inversiune cu toate elementele rămase în stânga deodată. Le numeri pe toate cu o singură adunare, fără să le compari una câte una.