Revizia anterioară Revizia următoare
In completarea Solutiei problemei Ordonare
O metoda de a obtine complexitate liniara (ignorand citirea si sortarea sirului) este ca in loc sa folosim un heap ($priority queue$) pentru a insera valorile date si a scoate minimul la fiecare pas, putem folosi o lista dublu inlantuita, astfel:
Lista, daca am parcurge-o de la stanga la dreapta, am vedea toate elementele din ceea ce ar fi fost inainte un heap, doar ca in ordine sortata. Mai mult, pe langa capetele listei, vom retine un iterator t care indica nodul din lista in dreptul caruia vrem sa inseram valoarea.
Deoarece valoarea pe care o inseram la fiecare pas este mai mare sau egala cu ultima valoare minus 1, iteratorul t va face cel mult un pas spre stanga, respectiv oricati pasi spre dreapta. Asta inseamna ca, amortizat, va face O(1) pasi. Inserarea in lista dublu inlantuita se face tot in O(1). Scoaterea minimului este si ea o operatie care muta capatul stanga al listei in O(1). Prin urmare solutia este liniara!
Dar daca in lista vom avea mai multe elemente egale la rand, nu cumva acel pas se poate sa le parcurga, de fapt, pe toate, atunci cand merge spre stanga? Desigur, daca nu compactam elementele egale, solutia este patratica. Compactarea se poate realiza tinand perechi de numere <valoare, frecventa>, astfel incat toate valorile din lista sunt diferite. Acum solutia este corecta.
