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  

Sortarea prin interclasare
Mulţi algoritmi utili au o structura recursiva: pentru a rezolva o problema data, aceştia sunt apelaţi de către ei înşişi o data sau de mai multe ori pentru a rezolva subprobleme apropiate.
Aceşti algoritmi folosesc de obicei o abordare de tipul divide şi stăpâneşte: ei rup problema de rezolvat în mai multe probleme similare problemei iniţiale, dar de dimensiune mai mica, le rezolva în mod recursiv şi apoi le combina pentru a crea o soluţie a problemei iniţiale.
Pentru metoda de sortare prin interclasare principiul  divide şi stăpâneşte poate fi privit astfel:
Divide: Împarte şirul de n elemente care urmează a fi sortat în doua subşiruri de câte n/2 elemente.
Stăpâneşte: Sortează recursiv cele doua subşiruri utilizând sortarea prin interclasare.
Combina: Interclasează cele două subşiruri sortate pentru a produce rezultatul final.

Figura 1.12 Modul de operare al sortării prin interclasare asupra vectorului A = {5, 2, 4, 6, 1, 3, 2, 6}.Lungimile şirurilor sortate, în curs de interclasare, cresc pe măsură ce algoritmul avansează de jos în sus.

Să observăm că recursivitatea se opreşte când şirul de sortat are lungimea 1, caz în care nu mai avem nimic de făcut, deoarece orice sir de lungime 1 este deja sortat.
Operaţia principala a algoritmului de sortare prin interclasare este interclasarea a două şiruri sortate, în pasul denumit mai sus “Combina”. Pentru aceasta vom utiliza o procedura auxiliara, Interclaseaza(A, p, q, r), unde A este un vector şi p, q şi r sunt indici ai vectorului, astfel încât p ≤ q < r. Procedura presupune că subvectorii A[p..q] şi A[q + 1..r] sunt sortaţi. Ea îi Interclasează pentru a forma un subvector sortat care înlocuieşte subvectorul curent A[p..r].
O procedura de tip Interclaseaza are un  de execuţie de ordinul Θ(n), în care n = r - p + 1 este numărul elementelor interclasate. Revenind la exemplul nostru cu cărţile de joc, să presupunem că avem doua pachete de cărţi de joc aşezate pe masa cu faţa în sus. Fiecare din cele doua pachete este sortat, cartea cu valoarea cea mai mica fiind deasupra.
Dorim să amestecam cele doua pachete într-un singur pachet sortat, care să rămână aşezat pe masa cu faţa în jos. Pasul principal este acela de a selecta cartea cu valoarea cea mai mica dintre cele doua aflate deasupra pachetelor (fapt care va face ca o noua carte să fie deasupra pachetului respectiv) şi de a o pune cu faţa în jos pe locul în care se va forma pachetul sortat final. Repetam acest procedeu până când unul din pachete este epuizat. În aceasta faza, este suficient să luam pachetul rămas şi să-l punem peste pachetul deja sortat întorcând toate cărţile cu faţa în jos.
Din punctul de vedere al timpului de execuţie, fiecare pas de baza durează un timp constant, deoarece comparam de fiecare data doar doua cărţi. Deoarece avem de făcut cel mult n astfel de operaţii elementare, timpul de execuţie pentru procedura Interclaseaza este Θ(n).


Subalgoritm Sorteaza-Prin-Interclasare(A, p, r)
1: daca p < r atunci
2:       q ← [(p + r)/2]
3:      Sorteaza-Prin-Interclasare(A, p, q)
4:      Sorteaza-Prin-Interclasare(A, q + 1, r)
5:      Interclaseaza(A, p, q, r)

Subalgoritm Interclaseaza(A, p, q, r)
i p;
j q + 1;
k1;
cat timp i q şi  j r executa
          daca  A[i] < A[j] atunci
                    C[k] A[i]
                    kk+1
                    ii+1
          altfel
                   C[k] A[j]
                   kk+1
                   jj+1
cat timp i q executa
                    C[k] A[i]
                    kk+1
                    ii+1
cat timp j r executa
                   C[k] A[j]
                   kk+1
                   jj+1
k1;
pentru i p, r executa
         A[i] C[k]
         kk+1

Utilizam procedura Interclaseaza ca subrutina pentru algoritmul de sortare prin interclasare. Procedura Sorteaza-Prin-Interclasare(A, p, r) sortează elementele dinsubvectorul A[p..r]. Daca p ¸ r, subvectorul are cel mult un element şi este, prin urmare, deja sortat. Altfel, pasul de divizare este prezent aici prin simplul calcul al unui indice q care împarte A[p..r] în doi subvectori, A[p..q] conţinând [n/2]+1elemente şi A[q + 1..r] conţinând [n/2]elemente.4 Pentru a sorta întregul sir A = {A[1],A[2], …A[n]}, vom apela procedura Sorteaza-Prin-Interclasare sub forma Sorteaza-Prin-Interclasare(A, 1, lungime[A]) unde, din nou, lungime[A] = n. Daca analizam modul de operare al procedurii, de jos în sus, când n este o putere a lui 2, algoritmul consta din interclasarea perechilor de şiruri de lungime 1, pentru a forma şiruri sortate de lungime 2, interclasarea acestora în şiruri sortate de lungime 4, şi aşa mai departe, până când doua şiruri sortate de lungime n/2 sunt interclasate pentru a forma şirul sortat final de dimensiune n. Figura 1.12 ilustrează acest proces.
Deşi algoritmul Sorteaza-Prin-Interclasare funcţionează corect când numărul elementelor nu este par, analiza bazata pe recurenţa se simplifica daca presupunem că dimensiunea problemei originale este o putere a lui 2. Fiecare pas de împărţire generează deci doua subşiruri având dimensiunea exact n=2.
Pentru a determina recurenţa pentru T(n), timpul de execuţie al sortării prin interclasare a n numere în cazul cel mai defavorabil, vom raţiona în felul următor. Sortarea prin interclasare a unui singur element are nevoie de un timp constant. Când avem n > 1 elemente, vom descompune timpul de execuţie dupa cum urmează:
Divide: La acest pas, se calculează doar mijlocul subvectorului, calcul care are nevoie de un timp constant de execuţie. Astfel, D(n) = Θ(1).
Stăpâneşte: Rezolvam recursiv doua subprobleme, fiecare de dimensiune n/2, care contribuie cu 2T(n/2) la timpul de execuţie.
Combina: Am observat deja că procedura Interclaseaza pentru un subvector cu n elemente consuma Θ(n) timp de execuţie, deci C(n) = Θ(n).
Când adunam funcţiile D(n) şi C(n) pentru analiza sortării prin interclasare, adunam o funcţie cu timpul de execuţie Θ(n) cu o funcţie cu timpul de execuţie Θ(1). Aceasta suma este funcţie liniara în raport cu n, adică are timpul de execuţie Θ(n). Adăugând aceasta la termenul 2T(n/2) de la pasul “Stăpâneşte”, obţinem timpul de execuţie T(n) în cazul cel mai defavorabil pentru sortarea prin interclasare:

Pentru numere suficient de mari, sortarea prin interclasare, având timpul de execuţie Θ(n log2 n), este mai performanta decât sortarea prin inserţie, al cărei timp de execuţie în cazul cel mai defavorabil este Θ(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 (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