Pagini recente » Diferente pentru utilizator/sulzandrei intre reviziile 23 si 15 | Diferente pentru problema/cartite intre reviziile 10 si 5 | Diferente pentru problema/order2 intre reviziile 17 si 18 | Diferente pentru utilizator/crazzytud intre reviziile 7 si 8 | Diferente pentru problema/sortare intre reviziile 19 si 6
Nu exista diferente intre titluri.
Diferente intre continut:
Cazul de baza a unei recursivitati sunt listele de dimensiune $0$ sau $1$. Putem implementa in pseudocod acest algoritm astfel:
==code(c)|functie qsort(sir[])
var stanga[], dreapta[], pivot
daca lungimea(sir) <= 1
returneaza sir
pivot = un element din sir
pentru fiecare x din sir
daca x < pivot atunci insereaza x in stanga
daca x > pivot atunci insereaza x in dreapta
returneaza concatenaeza(qsort(stanga), pivot, qsort(dreapta))
var stanga[], dreapta[], pivot
daca lungimea(sir) <= 1
returneaza sir
pivot = un element din sir
pentru fiecare x din sir
daca x < pivot atunci insereaza x in stanga
daca x > pivot atunci insereaza x in dreapta
returneaza concatenaeza(qsort(stanga), pivot, qsort(dreapta))
==
Fumeanu a implementat acest algoritm si considera ca implementarea lui este foarte eficienta. Nargy este mai intelept si isi da seama ca performanta intregului algoritm depinde de modul in care se selecteaza pivotul. Metoda folosita de Fumeanu este urmatoarea: pentru un sir de lungime $i$ el alege mediana elementelor de pe pozitiile $A{~i~}, B{~i~}$ si $C{~i~}$ (mediana reprezinta elementul mijlociu ca marime dintre cele $3$).
h2. Date de intrare
Fisierul de intrare $sortare.in$ contine pe prima linie numarul $N$. Pe urmatoarele $N-1$ linii se vor gasi cate 3 numere naturale $A{~i~} B{~i~} C{~i~}$ separate prin spatii ({$2≤i≤N$}).
Fisierul de intrare $sortare.in$ contine pe prima linie numarul $N$. Pe urmatoarele $N-1$ linii se vor gasi cate 3 numere natural $A{~i~} B{~i~} C{~i~}$ separate prin spatii ({$2≤i≤N$}).
h2. Date de iesire
1 3 4
1 3 5
| 3
1 2 3 4 5 |
1 2 3 4 5
|
h3. Explicatie
Pentru permutarea $1 2 3 4 5$ recursivitatea are $3$ nivele, astfel:
!problema/sortare?qsort.jpg!
Elementele ingrosate sunt cele care sunt folosite in determinarea pivotului, iar cele subliniate reprezinta pivotul. Nu exista nici o permutare de lungime $5$ care sa produca o adancime mai mare pentru datele de intrare date.
...
== include(page="template/taskfooter" task_id="sortare") ==
Nu exista diferente intre securitate.
Diferente intre topic forum: