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  

Metoda bulelor (bubble-sort)
Algoritmul constă în par­cur­ge­rea tabloului A de mai multe ori, până când devine or­do­nat. La fiecare pas se com­pa­ră două elemente alăturate. Dacă ai > ai + 1, (i = 1, 2, ..., n – 1), atunci cele două va­lori se interschimbă între ele. Controlul acţiunii repetitive este dat de variabila boole­a­nă ok, care la fiecare reluare a algoritmului primeşte valoarea ini­ţi­a­lă adevărat, care se schim­­bă în fals dacă s-a efectuat o interschimbare de două ele­men­te alăturate. În mo­men­tul în care tabloul A s-a parcurs fără să se mai efectueze nici o schim­bare, ok ră­mâ­ne cu valoarea iniţială adevărat şi algoritmul se termină, deoarece ta­bloul este or­do­nat.
Interschimbarea a două elemente se realizează prin intermediul variabilei auxiliare aux care are acelaşi tip ca şi elementele tabloului.


Subalgoritm  Metoda_bulelor (A)
1: repeta
2:     ok = adevărat
3:     pentru i=1,n-1 execută
4:           dacă a[i] > a[i+1] atunci
5:                  ok = fals
6:                  aux = a[i]
7:                  a[i] = a[i+1]
8:                  a[i+1] = aux
9: pana cand ok

Considerăm tabloul A cu 5 elemente numere reale: 0.0, 1.1, 1.0, 1.2 şi 0.08. Prima parcurgere a tabloului (ok este iniţializat cu adevărat):

a1 = 0.0

a2 = 1.1

a3 = 1.0

a4 = 1.2

a5 = 0.08

ok

0.0

1.0

1.1

1.2

0.08

fals

0.0

1.0

1.1

0.08

1.2

fals

Valorile 0.0 < 1.1, rămân neschimbate, 1.1 > 1.0, le interschimbăm. Deoarece 1.1 < 1.2, avansăm şi constatăm că 1.2 > 0.0.8, deci din nou avem interschimbare. În consecinţă, la ieşire din structura pentru ok este fals. Observăm că 1.2 a ajuns pe locul lui de­fi­nitiv. Urmează a doua parcurgere a ta­blo­ului (ok primeşte din nou valoarea adevărat).

a1 = 0.0

a2 = 1.0

a3 = 1.1

a4 = 0.08

a5 = 1.2

ok

0.0

1.0

0.08

1.1

1.2

fals

Am avut interschimbare şi de data aceasta, deci ieşim cu ok = fals. La acest pas 1.1 a ajuns pe locul său definitiv. A treia par­cur­ge­re a tabloului începe cu reiniţializarea lui ok cu valoarea adevărat.

a1 = 0.0

a2 = 1.0

a3 = 0.08

a4 = 1.1

a5 = 1.2

ok

0.0

0.08

1.0

1.1

1.2

fals

Am interschimbat 0.08 cu 1.0, cel din urmă astfel a ajuns pe locul său în şirul or­do­nat. A patra parcurgere a tabloului se finalizează cu valoarea ok = adevărat, deoarece nu am efectuat nici o interschimbare, ceea ce înseamnă că procesul de ordonare s-a în­che­iat.

a1 = 0.0

a2 = 0.08

a3 = 1.0

a4 = 1.1

a5 = 1.2

ok

0.0

0.08

1.0

1.1

1.2

adevărat

Observaţia cu privire la faptul că la fiecare parcurgere a ajuns cel puţin un element pe locul său definitiv în şirul ordonat poate fi fructificată, deoarece constatăm că ast­fel, la următorul pas nu mai sunt necesare verificările în care intervine acest ele­ment şi ce­le care se află după el în şir. Rezultă că la fiecare parcurgere am putea micşora cu 1 numărul elementelor verificate. Dar este posibil că la o parcurgere să ajungă mai multe elemente în locul lor definitiv. Rezultă că vom ţine minte indicele ultimului element care a intervenit în interschimbare şi verificările le vom efectua doar până la acest element. Astfel, ajungem la următorul subalgoritm îmbunătăţit ca performanţă:

Subalgoritm  Metoda_bulelor (A)
1: k=n {k va fi limita superioara pana unde se interschimba elemente}
2: repeta
3:     ok = adevărat
4:     pentru i=1,k-1 execută
5:           dacă a[i] > a[i+1] atunci
6:                  ok = fals
7:                  aux = a[i]
8:                  a[i] = a[i+1]
9:                  a[i+1] = aux
10:                j=i 
11:    k=j;  {ultimul indice pentru care s-a facut interchimbare}
12: pana cand ok

Metoda bulelor nu este cea mai performantă modalitate de a ordona un şir cu multe elemente, dar în cazul şirurilor „aproape ordonate”, cu optimizările de mai sus, poate deveni mai eficientă decât alte metode.
Pentru a analiza timpul de execuţie al metodei bulelor trebuie să luăm în considerare 3 mărimi:
1. numărul de treceri (parcurgeri)
2. numărul de interschimbări
3. numărul de comparaţii
Dacă presupunem că valorile de intrare reprezintă o permutare a mulţimii {1, 2, ..., n} putem uşor descrie efectul fiecărei treceri astfel: dacă un element ai nu are nici un precedent mai mare el va rămâne pe loc, iar daca are cel puţin unul mai mare atunci el se va muta cu o poziţie mai în faţă. Reamintesc că elementul maxim de la fiecare parcurgere va ajunge pe poziţia finală. Astfel, eficienţa metodei bulelor depinde de numărul de inversiuni din permutarea iniţială (faţă de permutarea finală, cea identică). Voi defini în continuare inversiunea şi proprietăţile inversiunilor.
Definiţie: Fie a1, a2, ... an o permutare a mulţimii {1, 2, ..., n}. Dacă i<j şi ai>aj, atunci perechea (ai, aj) se numeşte inversiunii a permutării. De exemplu, în permutarea 3,1,4,2 se găsesc 3 inversiuni: (3,1), (3,2) şi (4,2).
Observaţie: Singura permutare fără inversiuni este cea ordonată (identică) 1,2,...,n.      
Cazul cel mai favorabil este acela în care datele iniţiale sunt ordonate crescător, caz în care se face o singură parcurgerea a datelor.
Cazul cel mai nefavorabil este cel în care datele sunt sortate descrescător, caz în care se vor face n-1 parcurgeri. La prima parcurgere se vor face n-1 interschimbări, la a doua n-2 şi aşa mai departe. Aşadar numărul de comparaţii şi cel de interschimbări va fi n(n-1)/2. Exemplu în acest caz:


Numărul parcurgerii

a1

a2

a3

a4

Numărul de interschimbări

iniţial

4

3

2

1

 

1

3

2

1

4

3

2

2

1

3

4

2

3

1

2

3

4

1

Total interschimbări

6

Astfel, vom spune că metoda bulelor are un timp de execuţie în cazul cel mai defavorabil de Θ(n2).




  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