Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-09 [2017/02/24 11:03] mihai.iacov [1 Obiectivele laboratorului] |
laboratoare:laborator-09 [2017/02/27 20:17] mihai.iacov [4. Exercitii] |
||
---|---|---|---|
Linia 7: | Linia 7: | ||
* Heap Sort | * Heap Sort | ||
* Radix Sort | * Radix Sort | ||
+ | * qsort şi sort | ||
Propunem studierea următoarelor structuri auxiliare: | Propunem studierea următoarelor structuri auxiliare: | ||
- | *Heap (pentru Heap Sort) | + | *Heap-uri (pentru Heap Sort) |
| | ||
- | *deplasarea | + | *operaţii |
+ | | ||
- | =====2 | + | =====2. Introducere===== |
- | cuvântului conform principiului Divide et Impera, problema fiind descompusă în alte doua subprobleme de același tip | + | |
- | =====4 Exerciții propuse===== | + | ====2.1 Heap-uri==== |
+ | Există mai mutle tipuri de heap, dar ne vom referi numai la **binary heap** pentru implementarea algoritmului Heap sort. | ||
+ | Un heap binar este un arbore binar cu următoarele proprietăţi: | ||
+ | * este " | ||
+ | * există aceeaşi **relaţie de ordine** între orice nod şi părintele acestuia(excepţie - nodul rădăcină). | ||
+ | |||
+ | Dacă nodurile conţin numere întregi după care stabilim relaţia de ordine, heap-ul poate fi de două feluri: | ||
+ | * max-heap(rădăcina are cel mai mare număr, de la orice copil la părinte avem relaţia **mai mic sau egal**) | ||
+ | * min-heap(rădăcina are cel mai mic număr, de la orice copil la părinte avem relaţia **mai mare sau egal**) | ||
+ | |||
+ | |||
+ | ====2.2 Bucket-uri==== | ||
+ | |||
+ | Un pas din algoritmul Radix sort foloseşte o funcţie de indexare. Aceasta prelucrează cheia fiecărui element pentru a decide câte elemente să pună în fiecare sector(bucket). | ||
+ | * Sectoarele pot exista ca vectori independenţi sau ca un singur vector în care marcăm poziţia la care începe fiecare sector. | ||
+ | * Este recomandat ca funcţia de indexare să existe explicit(să fie definită ca subprogram) atunci când are o formă complicată. Dacă are o formă simplă(cum ar fi o singură operaţie), această parte poate fi omisă. | ||
+ | |||
+ | |||
+ | ====2.3 Operaţii pe biţi==== | ||
+ | |||
+ | Menţionăm următoarele operaţii pe biţi ce se pot folosi în C/C++ : | ||
+ | |||
+ | **Operaţii logice** | ||
+ | * & şi pe biţi(bitwise AND) | ||
+ | * | sau pe biţi(bitwise OR) | ||
+ | * ^ sau exclusiv pe biţi(bitwise XOR) | ||
+ | * ~ complement pe biţi(bitwise NOT) | ||
+ | |||
+ | **Deplasări** | ||
+ | * >> la dreapta(right shift) | ||
+ | * << la stânga(left shift) | ||
+ | |||
+ | Descriem numai operaţiile pe care le vom folosi în cadrul exemplului de mai jos: >> şi &. | ||
+ | * Operaţia n >> k are ca rezultat valoarea obţinută prin mutarea la dreapta a tuturor biţilor lui n(pe primii k biţi se obţine 0, iar ultimii k biţi din n sunt ignoraţi). | ||
+ | * Operaţia n & k are ca rezultat valoarea obţinută prin păstrarea biţilor nenuli din n pentru poziţiile pe care şi k are biţi nenuli(0 în rest) | ||
+ | |||
+ | <note tip> | ||
+ | Dacă n este număr **natural** şi k = 2< | ||
+ | * n >> p == n / k | ||
+ | * n & (k - 1) == n % k | ||
+ | |||
+ | Apar diferenţe în cazul numerelor negative. | ||
+ | </ | ||
+ | |||
+ | =====3. Algoritmii===== | ||
+ | |||
+ | ====3.1 Shell Sort==== | ||
+ | |||
+ | * timp mediu : O(N * log< | ||
+ | * timp la limită : O(N * log< | ||
+ | * memorie : O(1) | ||
+ | * Stabil : NU | ||
+ | |||
+ | |||
+ | === Descriere : === | ||
+ | |||
+ | Algoritmul shell sort este o generalizare a algoritmului insertion sort. | ||
+ | |||
+ | *La algoritmul insertion sort, pentru a insera un nou element în lista de elemente deja sortate, se deplasează fiecare element cu **câte o poziţie** spre dreapta atât timp cât avem elemente mai mari decât el. Practic, fiecare element înaintează spre poziţia sa finală cu câte o poziţie. | ||
+ | | ||
+ | *În prima iteraţie se aplică un insertion sort cu salt s1 mai mare decât 1. Asta înseamnă că fiecare element din şirul iniţial este deplasat spre stânga cu 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 se face cu saltul 1. Această ultimă iteraţie este practic un insetion sort clasic. | ||
+ | | ||
+ | |||
+ | === Implementare : === | ||
+ | |||
+ | <file cpp> | ||
+ | void shellSort(int a[],int n) | ||
+ | { | ||
+ | int i, j, k, h, v; | ||
+ | int cols[] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592, | ||
+ | 1968, 861, 336, 112, 48, 21, 7, 3, 1}; | ||
+ | for (k = 0; k < 16; k++) //parcurgem fiecare limita | ||
+ | { | ||
+ | h = cols[k]; //h = saltul | ||
+ | for (i = h; i < n; i++) //insertion sort | ||
+ | { | ||
+ | v = a[i]; | ||
+ | j = i; | ||
+ | while (j >= h && a[j-h] > v) //crescator | ||
+ | { | ||
+ | a[j] = a[j-h]; | ||
+ | j = j - h; | ||
+ | } | ||
+ | a[j] = v; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | Există mai multe variante propuse pentru vectorul cu salturi, iar complexitatea de timp diferă în funcţie de varianta aleasă. În general, complexitatea de timp asociată algoritmului Shell sort este O(N * log^2 N) şi o variantă destul de cunoscută cu această complexitate foloseşte vectorul obţinut din elementele mai mici decât N ale mulţimii A, puse în ordine descrescatoare, | ||
+ | </ | ||
+ | |||
+ | ==== 3.2 Heap Sort ==== | ||
+ | |||
+ | * timp mediu: O(N log N) | ||
+ | * timp la limită: O(N log N) | ||
+ | * memorie: O(1) | ||
+ | * Stabil: NU | ||
+ | |||
+ | === Descriere : === | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | *De exemplu, cu n/2 comparaţii se poate determina cheia mai mică pentru fiecare pereche de elemente dintre cele n elemente, apoi cu alte n/4 comparaţii se poate determina cheia cea mai mică pentru fiecare pereche ale cheilor determinate anterior, şi aşa mai departe. Astfel, cu **n-1** comparaţii se poate construi arborele de selecţie. | ||
+ | |||
+ | Descriem următorii paşi pentru o variantă de implementare a algoritmului Heap sort(ordonare crescătoare): | ||
+ | * presupunem că vectorul formează un arbore binar, fiecare poziţie din vector reprezentând un nod, cu **rădăcina** pe poziţia 0(**zero**) şi cu fiecare **nod k** având copiii **2k+1** şi **2k+2**(dacă nu există poziţia din vector cu indicele respectiv, atunci nu există nod copil => NULL) | ||
+ | * formăm un **max-heap** cu aceeaşi reprezentare(pe vector, fără a construi altă structură pentru noduri) | ||
+ | * extragem maximul din rădăcina heap-ului(poziţia 0 din vector) şi facem o intersschimbare între poziţia maximului şi ultima poziţie din vector. Acum maximul se află pe poziţia dorită şi putem să-l excludem din heap. | ||
+ | * repetăm paşii(refacem forma de heap, extragem noul maxim, reducem cu 1 numărul de elemente nesortate), cât timp mai sunt elemente în heap. | ||
+ | |||
+ | Definim următoarele două funcţii pentru a prezenta mai usor algoritmul Heap sort: | ||
+ | * funcţia " | ||
+ | * funcţia " | ||
+ | |||
+ | === Implementare : === | ||
+ | |||
+ | <file cpp> | ||
+ | void schimba(int a[],int i,int j) //functie auxiliara | ||
+ | { | ||
+ | int aux; | ||
+ | aux = a[i]; | ||
+ | a[i] = a[j]; | ||
+ | a[j] = aux; | ||
+ | } | ||
+ | void cerne(int a[],int n,int k) | ||
+ | { | ||
+ | int fiuStanga = 2 * k + 1, //pozitia primului copil | ||
+ | fiuDreapta = 2 * k + 2, | ||
+ | pozMax = fiuStanga; //pozitia copilului mai mare | ||
+ | if(fiuStanga >= n) | ||
+ | return; //" | ||
+ | if(fiuDreapta < n) { | ||
+ | if(a[fiuDreapta] > a[fiuStanga] ) { | ||
+ | pozMax = fiuDreapta; | ||
+ | } | ||
+ | }//am ales copilul mai mare | ||
+ | if(a[k] < a[pozMax]) { | ||
+ | schimba(a, | ||
+ | cerne(a, | ||
+ | } | ||
+ | } | ||
+ | void makeHeap(int a[],int n) //functia mai e numita " | ||
+ | { | ||
+ | //pentru i > n / 2, i este cu siguranta nod frunza | ||
+ | for(int i = n / 2;i >= 0;i--) { //ne asiguram ca exista ordine | ||
+ | cerne(a, | ||
+ | } | ||
+ | } | ||
+ | void heapSort(int a[],int n) | ||
+ | { | ||
+ | makeHeap(a, | ||
+ | while(n > 1) { | ||
+ | schimba(a, | ||
+ | n--; //am asezat un element pe pozitia finala | ||
+ | cerne(a, | ||
+ | //obtinem din nou forma de heap | ||
+ | } | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | <file cpp> | ||
+ | // | ||
+ | #include < | ||
+ | void heapSort(int a[], int n) //fara vector din STL | ||
+ | { | ||
+ | make_heap(a, | ||
+ | sort_heap(a, | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | <file cpp> | ||
+ | #include < | ||
+ | #include < | ||
+ | using namespace std; | ||
+ | void heapSort(int a[],int n) //cu vector din STL | ||
+ | { | ||
+ | int i; | ||
+ | vector< | ||
+ | for(int i = 0;i < n;i++) { //si am fi putut sari peste | ||
+ | v.push_back(a[i]); | ||
+ | } | ||
+ | make_heap(v.begin(), | ||
+ | sort_heap(v.begin(), | ||
+ | for(int i = 0;i < n;i++) { | ||
+ | a[i] = v[i]; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== 3.3 Radix Sort ==== | ||
+ | |||
+ | * timp mediu: O(N * k) | ||
+ | * timp la limită: O(N * k) | ||
+ | * memorie: O(N + k) | ||
+ | * Stabil: DA | ||
+ | |||
+ | k = lungimea cuvântului/ | ||
+ | |||
+ | Vom prezenta varianta LSD(Least Signifiant Digit) a algoritmului de sortare. | ||
+ | |||
+ | ===Descriere :=== | ||
+ | LSD Radix Sort este una dintre cele mai rapide metode de sortare.Aceasta se bazează pe | ||
+ | sortarea în funcţie de cea mai nesemnificativă " | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | Algoritmul trece prin următorii paşi: | ||
+ | | ||
+ | *pune fiecare element(în vectorul auxiliar) în secţiunea corespunzătoare, | ||
+ | | ||
+ | |||
+ | |||
+ | ===Implementare: | ||
+ | |||
+ | Exemplul prezentat foloseşte un octet pe post de " | ||
+ | <file cpp> | ||
+ | #define BYTE 8 | ||
+ | #define COUNT_BYTE 256 | ||
+ | int obtineOctetul(int n,int byteNr) | ||
+ | { // | ||
+ | //octetul de pe pozitia 0 este LSD = octetul cel mai din dreapta(pentru int) | ||
+ | int bitsNr = BYTE * byteNr; | ||
+ | int mask = COUNT_BYTE - 1; | ||
+ | return (n >> bitsNr) & mask; | ||
+ | } | ||
+ | void rad(int *a,int *b, int byteNr,int n) | ||
+ | { // | ||
+ | // pe pozitia 0 este LSD = octetul cel mai din dreapta | ||
+ | int i, | ||
+ | count[COUNT_BYTE] = {0}, //numaram cate elemente au " | ||
+ | index[COUNT_BYTE] = {0}; //pozitia la care vom pune urmatorul element cu " | ||
+ | for(i = 0; i < n;i++) { | ||
+ | int car = obtineOctetul(a[i], | ||
+ | count[car]++; | ||
+ | } | ||
+ | for(i = 1;i < COUNT_BYTE; | ||
+ | index[i] = index[i-1] + count[i-1]; | ||
+ | for(i = 0; i < n; i++) { //umplem sectiunile | ||
+ | int car = obtineOctetul(a[i], | ||
+ | b[index[car]++] = a[i]; | ||
+ | } | ||
+ | } | ||
+ | void radixSort(int *a,int n) | ||
+ | { | ||
+ | int *b = new int[n], //vector folosit la copiere | ||
+ | byteNr, //pozitia curenta | ||
+ | k = sizeof(a[0]); | ||
+ | for(byteNr = 0; byteNr < k; byteNr += 2) { | ||
+ | rad(a, b, byteNr, n); //in loc sa copiem b inapoi in a la fiecare pas | ||
+ | rad(b, a, byteNr + 1, n); //copiem doar o data la 2 pasi | ||
+ | } | ||
+ | delete []b; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | <note tip> | ||
+ | |||
+ | ===== 4. Exercitii ===== | ||
+ | |||
+ | ===1. Shell sort=== | ||
+ | |||
+ | E1. Creaţi un alt vector(mai simplu) pentru salturi, de exemplu: {1e5, | ||
+ | |||
+ | ===2. Heap sort=== | ||
+ | |||
+ | E2. Introduceţi o variabilă globală cu care să contorizaţi numărul de apelări ale funcţiei " | ||
+ | * Ce observaţi referitor la complexitatea funcţiilor? | ||
+ | |||
+ | ===3. Radix sort=== | ||
+ | |||
+ | E3. Încercaţi să sortaţi un vector cu orice numere întregi(pozitive şi negative). Verificaţi rezultatul şi adăugaţi un pas în algoritm pentru a aşeza corect elementele. | ||
+ | |||
+ | E4. Schimbaţi funcţia de indexare(obtineOctetul) şi valoarea lui k pentru a sorta un vector de şiruri de caractere. | ||
+ | |||
+ | E5. Se dă un vector cu n întregi, unde toate valorile din vector sunt cuprinse între 0 şi n^2 - 1. Sortaţi vectorul în timp O(n). | ||
+ | * Încercaţi să folosiţi altă " | ||