Sortarea constă în organizarea datelor în conformitate cu un algoritm matematic de distribuire. Sunt două tipuri de algoritmi de sortare:

Sortarea internă - utilizează doar resursele memoriei operative (ex. metoda selecţiei, metoda prin inserţie, metoda rapidă şi metoda bulelor)

Sortarea externă - utilizează memorie suplimentară.

Sortarea prin inserţie – constă în selectarea celui mai mic sau mai mare element şi plasarea lui la începutul masivului. Complexitatea acestui algoritm este de n2, unde n – nr. elementelor tabloului.

Sortarea prin selectie – constă în înserarea elementelor din tablou direct în poziţia sortată. Algoritmul constă în compararea fiecărui element cu precesorii săi şi poziţionarea lui în aşa fel încît tabloul să fie sortat. Complexitatea acestui algoritm este deasemenea n2

Sortarea prin metoda bulelor – constă în compararea a doua elemente alaturate şi scimbarea lor cu locul in caz de necesitate. Complexitatea - n2.Dezavantaj: este unul din cei mai lenţi algoritmi de sortare.Metoda poate fi imbunătăţită dacă: după fiecare trecere, se va reţine ultima poziţie din tablou în care a avut loc o interschimbare, iar trecerea următoare se va efectua doar pină la acea poziţie. În cazul în care la o trecere nu a avut loc nici o interschimbare algoritmul se va incheia.

Shaker Sort - Shaker sort (cocktail sort, shake sort) is a stable sorting algorithm with

quadratic asymptotic complexity  . Shakersort is a bidirectional version of bubble sort.Shaker sort unlike bubble sort orders the array in both directions. Hence every iteration of the algorithm consists of two phases. In the first one the lightest bubble ascends to the end of the array, in the second phase the heaviest bubble descends to the beginning of the array.

Parametri care reflecta eficienta

Algoritmii de sortare se deosebesc intre ei prin eficienta, timp de executie necesar, exprimat prin functia O. Sint folositi pentru aprecierea eficientei si: numarul compararilor de chei efectuate pentru sortare (C), mai ales atunci cind cheile sint siruri lungi de caractere si numarul miscarilor (asignarilor) de elemente (M),atunci cind dimensiunea elementelor tabloului este mare, in aceasta situatie fiind indicat ca pentru sortare sa se foloseasca un tablou paralel de cursori la elementele celui initial. Viteza unui algoritm este măsurată în diverse moduri. Cea mai simplă metodă utilizează complexitatea în timp pentru a determina Ordinul unui algoritm: de multe ori, este posibilă realizarea unui algoritm mai rapid în detrimentul spațiului utilizat. Spațiul unui algoritm este de fapt alcătuit din două lucruri separate dar în legătură. Prima parte este spațiul pe disc (sau echivalentul acestuia, depinzând de hardware și limbaj) ocupat de către executabilul compilat din codul sursă reprezentare a algoritului. Cealaltă parte măsurată a spațiului unui algoritm este cantitatea de memorie alocată temporar în timpul procesării. 

Shell SortComplexitatea : O(N * log^2 N)Algoritmul shell sort lucrează similar, doar că deplasează elementele spre poziţia finală cumai mult de o poziţie. Se lucrează în iteraţii. În prima iteraţie se aplică un insertion sort cu salts1 mai mare decât 1. Asta înseamnă că fiecare element din sirul iniţial este deplasat spre stângacu câte s1 poziţii atât timp cât întâlneste elemente mai mari decât el.Se repetă asemenea iteraţii cu salturi din ce în ce mai mici s2, s3, s4, etc. Ultima iteraţie seface cu saltul 1. Această ultimă iteraţie este practic un insetion sort clasic.Principiul este că după fiecare iteraţie sirul devine din ce în ce “mai sortat”. Iar cumalgoritmul insertion sort funcţionează cu atât mai repede cu cât sirul este mai sortat, peransamblu vom obţine o îmbunătăţire de viteză.Acest lucru se poate realiza dacă în loc de a compara elemente învecinate, comparăm elemente aflate

la o anumită distanţă între ele. în cazul în care ele nu sunt în ordinea cerută, ele se vor permuta. în felul

acesta elementele se deplasează făcând salturi mai mari decât o poziţie. Distanţa dintre elementele

comparate se numeşte increment.

incrementului iniţial egal cu n/2, unde n este numărul elementelor şirului de sortat. De asemenea, după fiecare parcurgere a şirului, acesta se va înjumătăţi.

2

Nr componente vector:7. înainte de ordonare:

****** SORT SHELL ******

Interschimbare element 0 cu 3, Increment 3

Interschimbare element 1 cu 4, Increment 3

Interschimbare element 2 cu 5, Increment 3

Interschimbare element 3 cu 6, Increment 3

Interschimbare element 0 cu 1, Increment 1

Interschimbare element 1 cu 2, Increment 1

Interschimbare element 3 cu 4, Increment 1

Interschimbare element 2 cu 3, Increment 1

Interschimbare element 4 cu 5, Increment 1

Interschimbare element 3 cu 4, Increment 1

După ordonare SHELL: v=

= 6 17 30 32 40 45

v = 46 30 32 40 6 17 45

40 30 32 46 6 17 45

40 6 32 46 30 17 45

40 6 17 46 30 32 45

40 6 17 45 30 32 46

6 40 17 45 30 32 46

6 17 40 45 30 32 46

6 17 40 30 45 32 46

6 17 30 40 45 32 46

6 17 30 40 32 45 46

6 17 30 32 40 45 46

3

HeapsortGasirea minimului din tablou, operatie ce are loc la fiecare pas, se bazeaza pe aducerea tabloului la forma de ansambluOrice tablou poate fi transformat usor intr-un arbore binarelementul minim se afla intotdeauna pe prima pozitieDaca nu este indeplinita una din conditiile Ai ≤ A2·i si Ai ≤ A2·i+1 atunci se va interschimba Ai cu minimul dintre A2·i si A2·i+1

Elementele astfel interschimbate vor indeplini conditia de ansambluPentru o eficienta cat mai mare, urmarirea acestui gen de situatii trebuie facuta de la dreapta la stanga, in caz contrar fiind nevoie de reveniri repetate chiar si dupa ce o situatie de neconcordanta a fost rezolvatadupa fiecare pas, primul element al tabloului, care este elementul minim, va fi eliminat si “pus la pastrare”, algoritmul continuand pe restul tabloului

La fiecare pas, tabloul scade cu un elementDe asemenea, se poate observa ca la fiecare pas, in afara de radacina arborelui, toate celelalte elemente indeplinesc deja conditia de ansamblu datorita pasului anteriorRezulta ca sarcina fiecarui pas nou este mult usurata de activitatea pasului/pasilor precedenti, ceea ce face ca algoritmul HeapSort sa fie foarte performantAlgoritmul HeapSort este cel mai slab algoritm de clasa O(N·log2N)Este mai slab (dar nu cu mult) decat algoritmii din familia QuickSort, dar are marele avantaj fata de acestia ca nu este recursivAlgoritmii recursivi ruleaza rapid, dar consuma o mare cantitate de memorie, ceea ce nu le permite sa sorteze tablouri de dimensiuni oricat de mariRepetand algoritmul de transformare a tabloului in ansamblu si eliminand dupa fiecare pas elementul minim obtinut (radacina arborelui), vom obtine in tabloul auxiliar elementele ordonate

Heapsort is the one of the most efficient comparison-based algorithms with the asymptotic

complexity  . Complexity of heapsort is guaranteed, hence it is fitting to use this algorithm in real time systems instead of quicksort, which is in average case faster, but its worst

case complexity is  . Heapsort is based on usage of the binary heap – data structure which acts as a priority queue. If we insert all elements of the array into the priority queue, the operation poll will always return (and remove) the element of the heap, which has the highest priority. If we use poll operation   times, we will obtain list of sorted elements.

The heapsort algorithm consists of these steps:

1. Build the heap using all elements of the array.2. Poll the highest element of the heap.3. Swap it with the last element of the heap (in array).4. Reduce the heap size by 1 (elements at the end of the heap are already sorted).5. Repair the heap (move element swapped in 3 to its correct place in the structure).6. If there are any elements remaining in the heap GOTO: 2.7. Array is sorted according to the priority of the elements in reverse order.

4

1. Starea initială a matricei 8 23 5 65 |44| 33 1 6

Pasul 1 (în calitate de x se alege a[5])

|--------|

8 23 5 6 44 33 1 65

|---|

8 23 5 6 1 33 44 65

Pasul 2 (în submatricea a[1], a[5] în calitate de x se alege a[3])

8 23 |5| 6 1 33 44 65

|--------|

1 23 5 6 8 33 44 65

|--|

1 5 23 6 8 33 44 65

Pasul 3 (în submatricea a[3], a[5] în calitate de x se alege a[4])

1 5 23 |6| 8 33 44 65

|----|

1 5 8 6 23 33 44 65

Pasul 4 (în submatricea a[3], a[4] se alege a[4])

1 5 8 |6| 23 33 44 65

|--|

1 5 6 8 23 33 44 65

Sortarea rapidă QuickSort – constă în împărţirea listei în două părţi ăn raport cu un pivot, în asa fel încît în partea stîngă a pivotului valorile să fie mai mici, iar în partea dreaptă mai mari. Complexitatea acestui algoritm este n*log(n).”. Ideea de bază a algoritmului constă în faptul că selectează la întîmplare un element x al matricei, după aceasta matricea se analizează din stînga, pînă cînd nu întîlneşte elementul a[i] astfel încît a[i]>x , şi apoi matricea se studiază din partea dreaptă, pînă cînd nu întîlneşte elementul a[j] astfel încît a[j]<x. Aceste 2 elemente sunt schimbate, precum şi procesul de vizualizare, compararea şi schimbul continuă pînă cînd vom ajunge la elementul x. În rezultat, matricea se divide în două părţi – stînga şi dreapta, în partea stînga valorile cheie vor fi mai mici decât x, iar în partea dreaptă valorile cheie vor fi mai mari decât x. În continuare procesul continuă recursiv pentru partea stîngă şi dreaptă a matricei, pînă cînd fiecare parte nu va conţine exact un element.

Structuri de date. Clasificarea. C versus C++.Clasificarea structurilor de date :I. Structuri de date elementare :- tablouri ( vectori, matrici, şiruri de caractere )

5

- înregistrare- mulţime- fişiereII. Structuri de date dinamice :- structura de tip listă ( listă simplu înlănţuită, dublu înlănţuită, circulară, stivă, coadă )- structura de tip arbore: arbori binari, arbori binari de cautare, arbori oarecare.III. Structuri de tip graf :- grafuri neorientate- arbori- grafuri orientate

So, if you believe me, we have established that "C++ is not significantly worse than C". Let's have a look at what it is that makes C++ a better C:

Stronger typing The type system in C++ is stronger than in C. This prevents many common programming errors - coupled with the next very important feature, the stronger type system even manages not to be an inconvenience.

Parameterized types The template keyword allows the programmer to write generic (type-agnostic) implementations of algorithms. Where in C, one could write a generic list implementation with an element like:A bigger standard library C++ allows the full use of the C standard library. This is very important of course, as the C standard library is an invaluable resource when writing real world programs. However, C++ includes the Standard Template Library. The STL contains a number of useful templates, like the sort routine above. It includes useful common data structures such as lists, maps, sets, etc

Algoritmi combinatoriali. Introducere.

Combinatorica –ramura care studiaza obiectele discrete in seturi.Se ocupa de studiul multimilor si modalitatile de a le combina. In particular sunt studiate :-combinatorica enumerativa(numarare);-design combinatoric si teoria matroizilor(generare si analiza);-combinatorica extremala(determinare a "celui mai mare", "celui mai mic" sau a "celui mai bun" obiect al mulțimii);-combinatorica algebrica(determinarea structural algebrice ale acelor obiecte);Combinatorica vizează atât rezolvarea de probleme cât și construcțiile teoretice, fiind dezvoltate metode teoretice puternice.Una din cele mai vechi și accesibile părți ale combinatoricii este teoria grafurilor, aceasta, la randul ei, având conexiuni cu multe alte domenii. Combinatorica este folosită frecvent in informatică pentru a estima numărul de elemente ale anumitor mulțimi.

Exemple de configurații combinatorice,algorimti combinatoriali:aranamente,permutari,combinari,produs cartezian, submulţimi ale unei mulţimi, partiţii ale unei mulţimi.

Pentru a formula și de a rezolva probleme combinatoriale, diverse modele de configurații combinatorice. Exemple de configurații combinatorice sunt:

5.Permutari, Combinari, Aranjamente

Permutarea este un concept matematic care se referă în mod uzual la numărul de posibilități de rearanjare al unei liste ordonate de valori sau obiecte.

6

Așadar o permutare poate fi înțeleasă ca unul din  n! moduri de a ordona liniar o mulțime. Însă în general nu este necesar ca obiectele permutate să fie ordonate liniar. Un alt exemplu este cel al unor bile diferit colorate, înșirate pe o sârmă închisă. Această situație va conduce la definiția abstractă, matematică, a permutării, în care nu mai sunt implicate ordinea sau alte determinări ale subiecților permutați.

Conceptul este studiat în cadrul combinatoricii. Aici conceptul poate extins prin conceptul de k-permutări sau aranjamente care arată numărul submulțimilor ordonate ale unei mulțimi date.

O permutare este o corespondență biunivocă (element la element sau bijecție) între o multime M (finită) și ea însăși.

Aranjamente

În practică, de multe ori se ajunge la necesitatea de a alege dintr-o mulțime oarecare de obiecte submulțimi care au anumite proprietăți sau de a aranja elementele unei mulțimi într-o numită ordine. Domeniul matematicii care studiază astfel de probleme se numește combinatorică și are importanță pentru teoria probabilităților, logica matematică, teoria numerelor, precum și pentru alte ramuri ale științei și tehnicii. Din această ramură a matematicii fac parte și aranjamentele.

Definiție: Daca   este o mulțime cu   elemente, atunci submulțimile ordonate ale lui  , având fiecare câte   elemente, unde  , se numesc aranjamente de   elemente luate câte  .\

COMBINARINumarul combinarilor a n elemente luate cate m este calculata cu formula:

6.Formule Herigonne, Pascal. Demonstratie. Exemple si aplicatii practice.

Sistemul major (de asemenea, numit,sistem mnemonic fonetic, sau sistemul mnemonic al lui Herigone) este o tehnică mnemonica utilizată pentru a ajuta la memorarea numerelor.Sistemul funcționează prin conversia numerelor în sunete consonantice, apoi în cuvinte prin adăugarea de vocale.Sistemul functioneaza pe principiul că imaginile pot fi memorizate mai ușor decât numerele. Fiecare cifră este asociata cu unul sau mai multe consoane. Vocalele și consoanele w, h, y și x sunt ignorate. Acestea pot fi utilizate ca "umplutură" pentru a face cuvinte sensibile din secvențele consonantice rezultate. Un avantaj al sistemului major este aceea că este posibil să se utilizeze la un calculator pentru a traduce automat numărul într-un set de cuvinte. Se poate alege apoi cel mai bun din mai multe alternative.

Cartografierea cea mai importanta este:

Numeral Associated Consonants Mnemonic

0 s, z, soft c "z" is the first letter of zero. The other letters have a similar sound.

7.Recursia. Algoritmi recursivi. Exemple:n!, nr Fibbonacci

7

În matematică și informatică, recursivitatea sau recursia este un mod de a defini unele funcții. Funcția este recursivă, dacă definiția ei folosește o referire la ea însăși, creând la prima vedere un cerc vicios, care însă este numai aparent, nu și real.

O funcţie este numită funcţie recursivă dacă ea se autoapelează, fie direct (în definiţia ei se face apel la ea însăşi), fie indirect (prin apelul altor funcţii). Limbajele C/C++ dispun de mecanisme speciale care permit suspendarea execuţiei unei funcţii, salvarea datelor şi reactivarea execuţiei la momentul potrivit. Pentru fiecare apel al funcţiei, parametrii şi variabilele automatice se memorează pe stivă, având valori distincte.

Un exemplu de funcţie recursivă este funcţia de calcul a factorialului, definită astfel:fact(n)=1, dacă n=0;fact(n)=n*fact(n-1), dacă n>0;`` 1Fie şirul lui Fibonacci, definit astfel: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2), dacă n>1. Să se scrie un program care implementează algoritmul de calcul al şirului Fibonacci atât recursiv, cât şi iterativ. Să se compare timpul de execuţie în cele două situaţii.

8