lsort

Lsort

h3. Explicatie pentru primul exemplu

* La pasul $1$, $L1$ = $[4, 1, 3, 2]$ si $L2$ = $[]$. Se sterge din $L1$ elementul $3$ (care se afla pe pozitia 3) si se introduce in L2. Costul acestei mutari este $3*1=3$.

* La pasul $1$, $L1$ = $[4, 1, 3, 2]$ si $L2$ = $[]$. Se sterge din $L1$ elementul $3$ (care se afla pe pozitia 3) si se introduce in $L2$. Costul acestei mutari este $3*1=3$.

* La pasul $2$, $L1$ = $[4, 1, 2]$ si $L2$ = $[ 3 ]$. Se sterge din $L1$ elementul $4$ (care se afla pe pozitia $1$) si se introduce in $L2$ (este evident ca acest element trebuie adaugat la sfarsitul listei $L2$ si nu la inceputul ei; in caz contrar, lista $L2$ nu ar mai fi sortata). Costul acestei mutari este $1*2=2$.
* La pasul $3$, $L1$ = $[1, 2]$ si $L2$ = $[3, 4]$. Se sterge din $L1$ elementul $2$ (care se afla pe pozitia $2$) si se introduce in $L2$ (din nou, pozitia unde trebuie adaugat elementul este evidenta : la inceputul listei L2). Costul acestei mutari este $2*3=6$.
* La pasul $4$, $L1$ = $[ 1 ]$ si $L2$ = $[2, 3, 4]$. Se sterge din $L1$ elementul $1$ (care se afla pe pozitia $1$) si se introduce in $L2$. Costul acestei mutari este $1*4=4$.
Costul total al constructiei listei $L2$ este $3+2+6+4=15$.
== include(page="template/taskfooter" task_id="lsort") ==

2151