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 prin numărarea apariţiilor

Algoritmii prezentaţi anterior sunt relativ mari consumatori de timp. De exemplu, pen­tru a ordona un şir de 1000 de elemente, numărul comparaţiilor pe care le va executa ori­­ca­re dintre algoritmii prezentaţi va fi aproximativ de 1 milion. Un algoritm liniar execută un număr de operaţii proporţional cu numărul ele­mentelor, adică pentru a ordona 1000 de elemente vor fi necesare c < 1000 de ope­ra­ţii, unde c este o constantă. În anumite condiţii asupra datelor de intrare se pot construi algoritmi liniari pentru sortare.

Dacă avem un şir de elemente de tip ordinal care sunt dintr-un interval de car­di­na­li­ta­te nu foarte mare, vom putea realiza o ordonare liniară. Corespunzător fie­că­rei va­lori întâlnite în şir în timpul prelucrării mărim cu 1 valoarea elementului având in­di­ce­le (în acest şir de contoare) egal cu valoarea elementului în şirul de ordonat. În final, vom suprascrie în şirul dat atâtea elemente cu valori ai indicilor elementelor diferite de 0 cât este valoarea elementului în acest şir a numerelor de apariţii.
Important este să reţinem particularităţile pe care trebuie să le aibă şirul dat pentru ca această metodă să se poată aplica:

  • valorile elementelor trebuie să fie de tip ordinal,
  • numărul elementelor mulţimii din care şirul primeşte valori trebuie să fie relativ mic, astfel încât, în funcţie de limbajul de programare în care vom implementa algoritmul să nu se depăşească memoria maximă alocată unui vector. 
  • valorile posibile în şirul de ordonat trebuie să fie din intervalul [x..y], unde yx + 1 va fi dimensiunea şirului de contoare.
Exemplu

Presupunem că toate valorile din vectorul de sortat sunt numere naturale <=1000. Vom folosi un vector de frecvenţe f.


Subalgoritm Ordonare_cu_Şir_de_Frecvenţe(n,a,x,y):
1: x  = 0
2: y = 1000
3: pentru i=x,y execută 
         f[i] = 0   {iniţializează frecvenţele cu 0}
4: pentru i=1,n execută:
      f[A[i]] = f[A[i]] + 1  {măreşte frecvenţa fiecărui element din A}
5: k = 0
6: pentru i=x,y execută:
7:        pentru j=1,f[i] execută:
8:              k = k + 1
9:              A[k] = i     {pune înapoi în A fiecare element de câte ori este frecvenţa lui}

Fie şirul (2, 1, 1, 0, 2, 3, 0, 2).
Şirul de frecvenţe construit de algoritmul de mai sus va fi va fi (2, 2, 3, 1).
Corespunzător ultimei secvenţe din algoritm se vor scrie două valori 0 consecutive în a, apoi 2 elemente egal cu 1, urmează trei elemente de 2, urmat de o valoare 3:  0, 0, 1, 1, 2, 2, 2, 3.
Deşi este un algoritm liniar, eficienţa lui trebuie bine studiată înainte de a-l aplica. Eficienta depinde atât de numărul de valori din vectorul iniţial, cât şi de valorile propriuzise. Algoritmul depinde liniar de n, numărul de valori din vector, dar capacitatea de memorie necesară pentru vectorul de frecvenţe şi apoi numărul de paşi ai instrucţiunii 6: depinde de limitele în care se află valorile din şir, iar în funcţie de acestea, algoritmul poate deveni mai puţin eficient decât unul cu ordin ce complexitate Θ(n2). Un exemplu în acest caz, dacă vrem să ordonăm 100 de numere din intervalul [1, 15000]. O ordonare Θ(n2) ar face maxim 10000 de paşi, iar ordonarea cu frecvenţe face 15000, ca să nu mai vorbim de risipa de memorie care se face în cazul folosirii vectorului de frecvenţe.

1.9.1.1. Sortarea prin numărarea apariţiilor şi a elementelor mai mici
Acest algoritm poate fi privit ca o variantă a algoritmului anterior, obţinută prin numărarea şi a elementelor mai mici, nu doar a frecvenţei de apariţie.
Sortarea prin numărare presupune că fiecare dintre cele n elemente ale datelor de intrare este un număr întreg între 1 şi k, pentru un număr întreg k oarecare. Când k = Θ(n), sortarea se executa în timpul Θ(n).
Ideea de baza în sortarea prin numărare este de a determina numărul de elemente mai mici decât x, pentru fiecare element x din datele de intrare. Acesta informaţie poate fi utilizata pentru a poziţiona elementul x direct pe poziţia sa din tabloul de ieşire. De exemplu, daca exista 17 elemente mai mici decât x, atunci x va fi pe poziţia 18 în tabloul de ieşire. Aceasta schema trebuie uşor modificata în situaţia în care exista mai multe elemente având aceeaşi valoare, întrucât nu dorim să le aşezam pe toate în aceeaşi poziţie.
În algoritmul pentru sortarea prin numărare presupunem că datele de intrare formează un tablou A[1..n], şi deci lungime [A] = n. Sunt necesare alte doua tablouri suplimentare, tabloul B [1..n], care cuprinde datele de ieşire sortate, şi tabloul C [1..k], pentru stocarea temporara în timpul lucrului.


Subalgoritm Sortare-Prin-Numarare(A,B, k)
1: pentru i ← 1, k executa
2:       C [i] 0
3: pentru j ← 1, lungime [A] executa
4:       C [A[j]] ← C [A[j]] + 1
5:           { C[i] conţine acum numarul elementelor egale cu i.}
6: pentru i ← 2, k executa
7:        C [i] ← C [i] + C [i - 1]
8:          { C[i] conţine numarul elementelor mai mici sau egale cu i.}
9: pentru j ← lungime [A] , 1,-1 executa
10:       B [C [A[j]]] ← A[j]
11:       C [A[j]] ← C [A[j]] - 1

Algoritmul de sortare prin numărare este ilustrat în figura 1.15. După iniţializarea din liniile1–2, în liniile 3–4 se contorizează fiecare element de intrare. Daca valoarea unui element de intrare este i, se incrementează valoarea lui C [i]. Astfel, dupa liniile 3–4, C[i] păstrează un număr de elemente de intrare egal cu i pentru fiecare număr întreg i = 1,2, … , k. În liniile 6–7 se determina, pentru fiecare i = 1, 2, … , k, numărul elementelor de intrare mai mici sau egale decât i, aceasta se realizează prin păstrarea în C[k] a sumei primelor k elemente din tabloul iniţial.
În final, în liniile 9–11, fiecare element A[j] se plasează pe poziţia sa corect determinata din tabloul de ieşire B, astfel încât acesta este ordonat. Daca toate cele n elemente sunt distincte, la prima execuţie a liniei 9, pentru fiecare A[j], valoarea C[A[j]] este poziţia finala corecta a lui A[j] în tabloul de ieşire, întrucât exista C [A[j]] elemente mai mici sau egale cu A[j]. Deoarece elementele ar putea să nu fie distincte, decrementam valoarea C[A[j]] de fiecare data când plasam o valoare A[j] în tabloul B, aceasta face ca următorul element de intrare cu o valoare egala cu A[j], daca exista vreunul, să meargă în poziţia imediat dinaintea lui A[j] în tabloul de  ieşire.
Cât timp necesita sortarea prin numărare? Bucla pentru din liniile 1–2 necesita timpul Θ(k), bucla pentru din liniile 3–4 necesita timpul Θ(n), bucla pentru din liniile 6–7 necesita timpul Θ(k), iar bucla pentru din liniile 9–11 necesita timpul Θ(n). Deci timpul total este Θ(k + n). În practica se utilizează sortarea prin numărare când avem k = Θ(n), caz în care timpul necesar este Θ(n).
O proprietate importanta a sortării prin numărare este stabilitatea: numerele cu aceeaşi valoare apar în tabloul de ieşire în aceeaşi ordine în care se găsesc în tabloul de intrare. Adică, legăturile dintre doua numere sunt distruse de regula conform căreia oricare număr care apare primul în vectorul de intrare, va apărea primul şi în vectorul de ieşire. Desigur, stabilitatea este importanta numai când datele învecinate sunt deplasate împreuna cu elementul în curs de sortare. Vom vedea în secţiunea următoare de ce stabilitatea este importanta.

Figura 1.15 Modul de funcţionare al algoritmului Sortare-Prin-Numarare pe un tablou A[1..8] de
intrare, unde fiecare element din tabloul A este un număr întreg pozitiv nu mai mare decât k = 6. (a) Tabloul A şi tabloul auxiliar C dupa liniei 4. (b) Tabloul C dupa executarea liniei 7. (c)-(e) Tabloul de ieşire B şi tabloul auxiliar C dupa unul, doua, respectiv trei iteraţii ale buclei din liniile 9–11. Doar elementele haşurate din tabloul B au fost completate. (f) Tabloul B sortat, furnizat la ieşire.




  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