Probleme de informatică
  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

   Home Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2018
Bacalaureat 2018 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2018
Subiecte si rezolvări 2010-2018
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Olimpiada
Clasele V-VI
Clasele VII-VIII
Clasa a IX-a
Clasa a X-a
Clasele XI-XII
Noţiuni teoretice
Metode de sortare
Metoda backtracking


Metode de sortare  

Sortarea rapidă (quick-sort)
Sortarea rapidă este un algoritm de sortare care, pentru un sir de n elemente, are un timp de execuţie Θ(n2), în cazul cel mai defavorabil. În ciuda acestei comportări proaste, în cazul cel mai defavorabil, algoritmul de sortare rapidă este deseori cea mai bună soluţie practică, deoarece are o comportare medie remarcabilă: timpul sau mediu de execuţie este Θ(n log2 n), şi constanta ascunsă în formula Θ(n log2 n) este destul de mica. Algoritmul are avantajul  că sortează pe loc (în spaţiul alocat şirului de intrare) şi lucrează foarte bine chiar şi într-un mediu de memorie virtuală.
Algoritmul conţine şi un subalgoritm important, folosit de sortarea rapidă pentru partiţionare.
Algoritmul de sortare rapidă, ca de altfel şi algoritmul de sortare prin interclasare, se bazează pe paradigma “divide şi stăpâneşte”. Iată un proces “divide şi stăpâneşte” în trei paşi, pentru un subşir A[p…r].
Divide: Şirul A[p..r] este împărţit (rearanjat) în doua subşiruri nevide A[p..q] şi A[q + 1..r], astfel încât fiecare element al subşirului A[p..q] să fie mai mic sau egal cu orice element al subşirului A[q + 1..r]. Indicele q este calculat de procedura de partiţionare.
Stăpâneşte: Cele două subşiruri A[p..q] şi A[q + 1..r] sunt sortate prin apeluri recursive ale algoritmului de sortare rapidă.
Combina: Deoarece cele două subşiruri sunt sortate pe loc, nu este nevoie de nici o combinare, şirul A[p..r] este ordonat.
Descrierea algoritmului este următoarea:


Subalgoritm  Quicksort(A, p, r)
1: daca p < r atunci
2:       q =Partiţie(A, p, r)
3:      Quicksort(A, p, q)
4:      Quicksort(A, q + 1, r)

Pentru ordonarea întregului sir A, iniţial se apelează Quicksort(A, 1, lungime[A]).
Cheia algoritmului este procedura Partiţie, care rearanjează pe loc subşirul A[p..r].


Subalgoritm  Partiţie(A, p, r)
1: x = A[p]
2: i = p - 1
3: j = r + 1
4: cât timp i<j executa
5:       repeta
6:             j = j - 1
7:       pâna când A[j] ≤ x
8:       repeta
9:             i = i + 1
10:     pâna când A[i] ≥ x
11:     daca i < j atunci
12:          interschimba A[i] ↔ A[j]
13: returneaza j

În figura 1.3 este ilustrat modul de funcţionare a procedurii Partiţie. Întâi se selectează un element x = A[p] din şirul A[p..r], care va fi elementul “pivot”, în jurul căruia se face partiţionarea şirului A[p..r]. Apoi, doua subşiruri A[p..i] şi A[j..r] cresc la începutul şi respectiv, sfârşitul şirului A[p..r], astfel încât fiecare element al şirului A[p..i] să fie mai mic sau egal cu x, şi orice element al şirului A[j..r], mai mare sau egal cu x. La început i = p - 1 şi j = r + 1, deci cele două subşiruri sunt vide.
În interiorul ciclului cât timp, în liniile 5–7, indicele j se decrementează, iar  se incrementează până când A[i] ≥ x ≥ A[j]. Presupunând că inegalităţile de mai sus sunt stricte, A[i] este prea mare ca să aparţină primului subşir (cel de la început), iar A[j] prea mic ca să aparţină celui de al doilea subşir (cel de la sfârşit). Astfel, interschimbând A[i] cu A[j] (linia 12), cele doua parţi cresc. (Interschimbarea se poate face şi în cazul în care avem inegalităţi stricte.) Ciclul cât timp se repeta până când inegalitatea i ≥ j devine adevărata. În acest moment, întregul sir A[p..r] este partiţionat în doua subşiruri A[p..q] şi A[q + 1..r], astfel încât p ≤ q < r şi nici un element din A[p..q] nu este mai mare decât orice element din A[q + 1..r]. Procedura returnează valoarea q = j.
De fapt, procedura de partiţionare executa o operaţie simplă: pune elementele mai mici decât x în primul subşir, iar pe cele mai mari decât x în subşirul al doilea. Exista câteva particularităţi care determina o comportare interesanta a procedurii Partiţie. De exemplu, indicii i şi j nu depăşesc niciodată marginile vectorului A[p..r], dar acest lucru nu se vede imediat din textul procedurii.
Timpul de execuţie al procedurii Partiţie, în cazul unui vector A[p..r], este Θ(n),

Figura 1.3 Operaţiile efectuate de procedura Partiţie pe un exemplu. Elementele haşurate în gri deschis sunt deja plasate în poziţiile lor corecte, iar cele haşurate închis încă nu. (a) Şirul de intrare, cu valorile iniţiale ale variabilelor i şi j, care punctează în afara şirului. Vom face partiţionarea în jurul elementului x = A[p] = 5. (b) Poziţiile lui i şi j în linia 11 a algoritmului, dupa prima parcurgere a ciclului cât timp. (c) Rezultatul schimbului de elemente descris în linia 12. (d) Valorile lui i şi j în linia 11 dupa a doua parcurgere a ciclului cât timp. (e) Valorile lui i şi j dupa a treia şi ultima iteraţie a ciclului cât timp. Procedura se termina deoarece i ¸ j şi valoarea returnata este q = j. Elementele şirului până la A[j], inclusiv, sunt mai mici sau egale cu x = 5, iar cele de dupa A[j], sunt toate mai mari sau egale cu x = 5.

Timpul de execuţie al algoritmului de sortare rapidă depinde de faptul că partiţionarea este echilibrata sau nu, iar acesta din urmă de elementele alese ca „pivot” pentru partiţionare. Daca partiţionarea este echilibrata, algoritmul este la fel de rapid ca sortarea prin interclasare. În cazul în care partiţionarea nu este echilibrată, algoritmul se executa la fel de încet ca sortarea prin inserare. În aceasta secţiune vom investiga, fără rigoare matematica, performanţa algoritmului de sortare rapidă în cazul partiţionării echilibrate.

Figura 1.4 Arborele de recursivitate pentru Quicksort când procedura Partiţie pune întotdeauna într-o parte a vectorului numai un singur element (cazul cel mai defavorabil). Timpul de execuţie în acest caz este Θ(n2).

Partiţionarea în cazul cel mai defavorabil
Comportarea cea mai defavorabilă a algoritmului de sortare rapidă apare în situaţia în care procedura de partiţionare produce un vector de n-1 elemente şi unul de 1 element.
Să presupunem că această partiţionare dezechilibrată apare la fiecare pas al algoritmului. Deoarece timpul de partiţionare este de Θ(n), şi T(1) = Θ(1), formula recursiva pentru timpul de execuţie a algoritmului de sortare rapidă este:
T(n) = T(n - 1) + Θ(n):
Pentru evaluarea formulei de mai sus, observam că T(1) = Θ(1), apoi iterăm formula:

Ultima egalitate se obţine din observaţia că ultima sumă este o progresie aritmetică.
În figura 1.4 este ilustrat arborele de recursivitate pentru acest cel mai defavorabil caz al algoritmului de sortare rapidă. Daca partiţionarea este total dezechilibrata la fiecare pas recursiv al algoritmului, atunci timpul de execuţie este Θ(n2). Deci timpul de execuţie, în cazul cel mai defavorabil, nu este mai bun decât al algoritmului de sortare prin inserare, de exemplu. Mai mult, timpul de execuţie este Θ(n2) chiar şi în cazul în care vectorul de intrare este ordonat – caz în care algoritmul de sortare prin inserare are timpul de execuţie Θ(n).
Partiţionarea în cazul cel mai favorabil
Daca algoritmul de partiţionare produce doi vectori de n/2 elemente, algoritmul de sortare rapidă lucrează mult mai repede.

Figura 1.5 Arborele de recurenţă pentru Quicksort când procedura Partiţie produce întotdeauna parţi egale (cazul cel mai favorabil). Timpul de execuţie rezultat este Θ(n log2 n).

Formula de recurenţa în acest caz este: T(n) = 2T(n/2) + Θ(n), iar soluţia este T(n) = Θ(n log2 n). Deci partiţionarea cea mai buna produce un algoritm de sortare mult mai rapid. În figura 1.5 se ilustrează arborele de recursivitate pentru acest cel mai favorabil caz. Partiţionarea echilibrată arată că timpul mediu de execuţie a algoritmului de sortare rapidă este mult mai apropiat de timpul cel mai bun decât de timpul cel mai rău. Pentru a înţelege de ce este aşa, ar trebui să studiem efectul partiţionării echilibrate asupra formulei recursive care descrie timpul de execuţie.
Să presupunem că procedura de partiţionare produce întotdeauna o împărţire în proporţie de 9 la 1, care la prima vedere pare a fi o partiţionare dezechilibrata. În acest caz, formula recursivă pentru timpul de execuţie al algoritmului de sortare rapidă este:
T(n) = T(9n/10) + T(n/10) + n
unde, pentru simplificare, în loc de Θ(n) s-a pus n. Arborele de recurenţa corespunzător se găseşte în figura 1.6. Să observam că la fiecare nivel al arborelui costul este n până când la adâncimea log10 n = Θ(log2 n) se atinge o condiţie iniţială. În continuare, la celelalte niveluri, costul nu depăşeşte valoarea n. Apelul recursiv se termina la adâncimea log10/9 n = Θ(log2 n).

Figura 1.6 Arborele de recurenţa pentru Quicksort, când procedura Partiţie produce întotdeauna
parţi în proporţie de 9 la 1, rezultând un timp de execuţie de Θ (n log2 n).

Costul total al algoritmului de sortare rapidă este deci Θ(n log2 n). Ca urmare, cu o partiţionare în proporţie de 9 la 1 la fiecare nivel al partiţionării (care intuitiv pare a fi total dezechilibrata), algoritmul de sortare rapidă are un timp de execuţie de Θ(n log2 n) – asimptotic acelaşi ca în cazul partiţionării în două parţi egale. De fapt, timpul de execuţie va fi Θ(n log2 n) şi în cazul partiţionării într-o proporţie de 99 la 1. La orice partiţionare într-o proporţie constanta, adâncimea arborelui de recursivitate este Θ(log2 n) şi costul, la fiecare nivel, este Θ(n). Deci timpul de execuţie este Θ(n log2 n) la orice partiţionare într-o proporţie constantă.

 

Intuirea comportării medii
Pentru a avea o idee clara asupra comportării medii a algoritmului de sortare rapidă, trebuie să facem presupuneri asupra frecvenţei anumitor intrări. Cea mai evidenta presupunere este că toate permutările elementelor de intrare sunt la fel de probabile. Vom discuta aceasta presupunere în secţiunea următoare, aici vom exploata doar câteva variante.
În situaţia în care algoritmul de sortare rapidă lucrează pe o intrare aleatoare, probabil că nu va partiţiona la fel la fiecare nivel, cum am presupus în discuţiile anterioare. Este de aşteptat ca unele partiţionări să fie echilibrate, altele nu.
În cazul mediu, procedura Partiţie produce un amestec de partiţionări “bune” şi “rele”. Într-un arbore de recurenţa pentru cazul mediu al procedurii Partiţie, partiţionările bune şi rele sunt distribuite aleator. Să presupunem, totuşi, pentru simplificare, că partiţionările bune şi rele alternează pe niveluri, şi că partiţionările bune corespund celui mai bun caz, iar cele rele celui mai defavorabil caz. În figura 1.7 sunt prezentate partiţionările la doua niveluri consecutive în arborele de recursivitate. Costul partiţionării la rădăcina arborelui este n, iar vectorii obţinuţi sunt de dimensiune n - 1 şi 1: cazul cel mai defavorabil. La nivelul următor, vectorul de n - 1 elemente se împarte în doi vectori de (n - 1)/2 elemente fiecare, potrivit cazului celui mai bun.
Să presupunem că pentru un vector de dimensiune 1 (un element) costul este 1.
Combinarea unei partiţionări rele şi a uneia bune produce trei vectori de dimensiune 1, (n - 1)/2 şi respectiv (n - 1)/2, cu un cost total de 2n - 1 = Θ(n). Evident, aceasta situaţie nu este mai rea decât cea prezentata în figura 1.7 (b), adică cea cu un singur nivel, care produce un vector de (n - 1)/2 + 1 elemente şi unul de (n - 1)/2 elemente, cu un cost total de n = Θ(n).
Totuşi, situaţia din urmă este aproape echilibrată, cu siguranţă mult mai bună decât proporţia 9 la 1. Intuitiv, o partiţionare defavorabila de un cost Θ(n) poate fi absorbită de una buna tot de un cost Θ(n), şi partiţionarea rezultata este favorabila. Astfel timpul de execuţie al algoritmului de sortare rapidă, când partiţionările bune şi rele alternează, este acelaşi ca în cazul partiţionărilor bune: tot Θ (n log2 n), doar constanta din notaţia Θeste mai mare.

Figura 1.7 (a) Două niveluri ale arborelui de recurenţă pentru algoritmul de sortare rapidă. Partiţionarea la nivelul rădăcinii consumă n unităţi de timp şi produce o partiţionare “proastă”: doi vectori de dimensiune 1 şi n - 1. Partiţionarea unui subşir de n - 1 elemente necesita n - 1 unităţi de timp şi este o partiţionare “bună”: produce doua subşiruri de (n - 1)/2 elemente fiecare. (b) Un singur nivel al arborelui de recurenţa care este mai rău decât nivelurile combinate de la (a), totuşi foarte bine echilibrat.




  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

Calculatoare si accesorii second hand
Copyright 2009-2017 Muresan Vasile Ciprian - mcip.ro