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  

Ordonarea pe grupe
Ordonarea pe grupe se executa, în medie, în timp liniar. Ca şi sortarea prin numărare, ordonarea pe grupe este rapidă pentru ca face anumite presupuneri despre datele de intrare. În timp ce sortarea prin numărare presupune că intrarea consta din întregi dintr-un domeniu mic, ordonarea pe grupe presupune că intrarea este generata de un proces aleator care distribuie elementele în mod uniform în intervalul [0, 1).
Principiul algoritmului de ordonare pe grupe este de a împarţi intervalul [0, 1) în n subintervale egale, numite grupe (engl. buckets) şi apoi să distribuie cele n numere de intrare în aceste grupe. Întrucât datele de intrare sunt uniform distribuite în intervalul [0, 1), nu ne aşteptăm să fie prea multe numere în fiecare grupa. Pentru a obţine rezultatul dorit, sortam numerele din fiecare grupa, apoi trecem prin fiecare grupa în ordine, listând elementele din fiecare.
Pseudocodul pentru ordonarea pe grupe presupune că datele de intrare formează un tablou A având n elemente şi ca fiecare element A[i] satisface relaţia 0 ≤ A[i] < 1. Codul necesita un tablou auxiliar B[0..n-1] de liste înlănţuite (reprezentând grupele) şi presupune că exista un mecanism pentru menţinerea acestor liste.


Subalgoritm Ordonare-Pe-Grupe(A)
1: n ← lungime[A]
2: pentru i ←1, n executa
3:         insereaza A[i] în lista B [[nA[i]]]
4: pentru i ←0, n - 1 executa
5:         sorteaza lista B[i] folosind sortarea prin inserţie
6: concateneaza în ordine listele B [0] , B [1] , …,B [n - 1]

Pentru a demonstra că acest algoritm funcţionează corect, se considera doua elemente A[i] şi A[j]. Daca aceste elemente sunt distribuie în aceeaşi grupa, ele apar în ordinea relativa adecvata în secvenţa de ieşire, deoarece grupa lor este sortata de sortarea prin inserţie. Să presupunem, totuşi, că ele sunt distribuite în grupe diferite. Fie aceste grupe B[i0] şi respectiv B[j0], şi să presupunem, fără a pierde din generalitate, că i0 < j0. Când listele lui B sunt concatenate în linia 6, elementele grupei B[i0] apar înaintea elementelor lui B [j0], şi astfel A[i] precede A[j] în secvenţa de ieşire. Deci trebuie să arătăm că A[i] ≤ A[j]. Presupunând contrariul, avem i0 = [nA[i]][nA[j]]= j0, ceea ce este o contradicţie, întrucât i0 < j0. Aşadar, ordonarea pe grupe funcţionează corect.
Pentru a analiza timpul de execuţie, să observam mai întâi că toate liniile, cu excepţia liniei 5, necesita, în cel mai defavorabil caz, timpul O(n). Timpul total pentru a examina în linia 5 toate grupele este O(n) şi, astfel, singura parte interesanta a analizei este timpul consumat de sortările prin inserţie din linia 5.
Pentru a analiza costul sortărilor prin inserţie, fie ni o variabila aleatoare desemnând numărul de elemente din grupa B[i]. Întrucât sortarea prin inserţie se executa în timp pătratic, timpul necesar sortării elementelor în grupele B [i] este E [O(ni2)] = O(E[ni2])
În consecinţa, timpul mediu total necesar sortării tuturor elementelor în toate grupele va fi

Figura 1.17 ilustrează modul de funcţionare al algoritmului de ordonare pe grupe pe un tablou de intrare cu 10 numere.

Figura 1.17 Funcţionarea algoritmului Ordonare-Pe-Grupe. (a) Tabloul de intrare A[1..10]. (b) Tabloul B[0..9] al listelor (reprezentând grupele) sortate dupa linia a cincea a algoritmului. Grupa I cuprinde valorile din intervalul [i=10, (i + 1)=10). Ieşirea sortata consta dintr-o concatenare în ordine a listelor B [0], B [1] , ..:,B [9].




  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