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 (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
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 (12)

   Home Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2017
Bacalaureat 2017 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2017
Subiecte si rezolvări 2010-2017
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
Teme proiect
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Subiecte atestat 2014 CNLR
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  

Sortare prin selecţie directă
Metoda precedentă are dezavantajul că necesită de două ori mai multă memorie decât tabloul A. Dacă dorim să evităm această risipă, putem aplica metoda de ordonare prin selectarea unui element şi plasarea lui pe poziţia sa finală direct în tabloul A.
De exemplu, în caz de ordonare crescătoare, pornind de la primul element se caută va­loarea minimă din tablou. Aceasta se aşează pe prima poziţie printr-o in­ter­schim­ba­re între elementul de pe prima poziţie şi elementul minim. Apoi, se reia algoritmul, por­nind de la a doua poziţie şi se caută minimul între elementele a2, ..., an. Acesta se inter­schimbă cu al doilea dacă este cazul. Procedeul se continuă până la ultimul ele­ment.
Pseudocodul algoritmului de sortare prin selecţia minimului este:


Subalgoritm Selecţie(n,a)
1:  pentru i=1,n-1 execută:
2:      min = a[i]
3:      pentru j=i+1,n execută:
4:            dacă min > a[j] atunci
5:                 min = a[j]
6:                 k = j
7:      dacă min <> a[i] atunci
8:           aux = a[i]
9:           a[i] = a[k]
10:         a[k] = aux
Exemplu

Fie tabloul A = (5, 0, 8, 7, 3).

Pas

Tabloul A

Element minim

Poziţia minimului

Noul tablou A

1

(5, 0, 8, 7, 3)

0

2

(0, 5, 8, 7, 3)

2

(0, 5, 8, 7, 3)

3

5

(0, 3, 8, 7, 5)

3

(0, 3, 8, 7, 5)

5

5

(0, 3, 5, 7, 8)

4

(0, 3, 5, 7, 8)

7

4

 

Algoritmul se poate scrie şi prin determinarea valorilor maxime şi mutarea lor în tablou de la dreapta la stânga, astfel rezultând, de asemenea, un şir ordonat crescător. Un astfel de algoritm este des utilizat pentru că este mai simplu de reţinut, în forma următoare:


Subalgoritm Selecţie(n,a)
1:  pentru i=1,n-1 execută:
2:      pentru j=i+1,n execută:
3:            dacă a[i] > a[j] atunci
4:                       aux = a[i]
5:                       a[i] = a[j]
6:                       a[j] = aux

Pentru acest algoritm de sortare nu putem spune că există caz favorabil, nefavorabil sau mediu, deoarece numărul de paşi efectuaţi este n(n-1)/2 indiferent de structura datelor de intrare. Aşadar, ordinul de complexitate este Θ(n2). Numărul de comparări este tot n(n-1)/2, însă pentru cazul în care şirul este ordonat crescător se vor face doar n atribuiri (se execută doar instrucţiunea de atribuire 2:)




  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 (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
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 (12)

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