Unelte utilizator

Unelte site


laboratoare:laborator-09

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-09 [2017/02/25 17:05]
mihai.iacov [3.3 Radix Sort]
laboratoare:laborator-09 [2017/04/27 21:18]
iulian.matesica
Linia 1: Linia 1:
 ====== Laborator 09: Algoritmi de sortare 2 ====== ====== Laborator 09: Algoritmi de sortare 2 ======
-\\+
 =====1 Obiectivele laboratorului===== =====1 Obiectivele laboratorului=====
  
Linia 12: Linia 12:
  *Heap-uri (pentru Heap Sort)  *Heap-uri (pentru Heap Sort)
  *vector de sectoare - bucket-uri (pentru Radix Sort)  *vector de sectoare - bucket-uri (pentru Radix Sort)
- *deplasarea pe biţi(operaţia **bit shift**) + *operaţii pe biţi 
- *Pachetul STL -> <algorithm>+ *Pachetul STL(Standard Template Library) -> <algorithm>
  
 =====2. Introducere===== =====2. Introducere=====
  
 ====2.1 Heap-uri==== ====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 "complet"(toate nivelele sunt pline, cu posibila excepţie a ultimului nivel), adică de **înălţime minimă**
 +  * 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==== ====2.2 Bucket-uri====
  
-====2.3 Bit Shift====+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<sup>p</sup>, atunci: 
 +  * n >> p == n / k 
 +  * n & (k - 1) == n % k 
 + 
 +Apar diferenţe în cazul numerelor negative. 
 +</note>
  
 =====3. Algoritmii===== =====3. Algoritmii=====
Linia 86: Linia 126:
  *Această sortare se poate îmbunătăţi prin reţinerea, de la fiecare scanare, de mai multă informaţie decât identificarea unui singur element, cel mai mic.  *Această sortare se poate îmbunătăţi prin reţinerea, de la fiecare scanare, de mai multă informaţie decât identificarea unui singur element, cel mai mic.
  *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.  *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.
- *Exemplul ne dă o idee despre cum este implementată funcţia **make_heap**+ 
 +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ă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 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 "**cerne**"(asigură "cernerea"/"scurgerea"/"căderea" nodului k până poziţia necesară pentru heap) - dacă nodul k nu are valoarea mai mare decât a copiilor lui(nu se păstrează relaţia de ordine a heap-ului), atunci nodul k va fi "cernut" până va fi respectată relaţia. 
 +  * funcţia "**makeHeap**"(formează max heap-ul) - funcţia cerne toate nodurile pentru a obţine un heap
  
 === Implementare : === === Implementare : ===
  
 <file cpp> <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; //"nodul" k este frunza
 +    if(fiuDreapta < n) {
 +        if(a[fiuDreapta] > a[fiuStanga] ) {
 +            pozMax = fiuDreapta;
 +        }
 +    }//am ales copilul mai mare
 +    if(a[k] < a[pozMax]) {
 +        schimba(a,k,pozMax); //nodul k este "cernut" - coboara
 +        cerne(a,n,pozMax); //cernem la noua lui pozitie
 +    }
 +}
 +void makeHeap(int a[],int n) //functia mai e numita "heapify"
 +{
 +    //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,n,i); // pentru orice nod de la i la n-1
 +    }
 +}
 +void heapSort(int a[],int n)
 +{
 +    makeHeap(a,n); //construim un heap
 +    while(n > 1) {
 +        schimba(a,0,n-1); //mutam maximul pe ultima pozitie
 +        n--; //am asezat un element pe pozitia finala
 +        cerne(a,n,0); //elementul pus in locul maximului trebuie "cernut"
 +        //obtinem din nou forma de heap
 +    }
 +
 +}
 +</file>
 +<file cpp>
 +//implementare STL
 #include <algorithm> #include <algorithm>
 void heapSort(int a[], int n) //fara vector din STL void heapSort(int a[], int n) //fara vector din STL
 { {
-    make_heap(a,a + n); +    make_heap(a,a + n);//pointer catre primul element si pointer 
-    sort_heap(a,a + n);+    sort_heap(a,a + n);//catre primul bloc de memorie de după vector
 } }
 </file> </file>
Linia 144: Linia 238:
 ===Implementare:=== ===Implementare:===
  
 +Exemplul prezentat foloseşte un octet pe post de "caracter". Putem interpreta acest exemplu şi ca scriere a numerelor în baza 256, valoarea fiecărui octet fiind o "cifră"
 +<file cpp>
 +#define BYTE 8
 +#define COUNT_BYTE 256
 +int obtineOctetul(int n,int byteNr)
 +{   //cautam octetul de la pozitia 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)
 +{   //sortare dupa octetul de pe pozitia byteNr,
 +    // pe pozitia 0 este LSD = octetul cel mai din dreapta
 +    int i,
 +        count[COUNT_BYTE] = {0}, //numaram cate elemente au "car." i pe pozitia byteNr
 +        index[COUNT_BYTE] = {0}; //pozitia la care vom pune urmatorul element cu "car." i
 +    for(i = 0; i < n;i++) {
 +        int car = obtineOctetul(a[i],byteNr);
 +        count[car]++;
 +    }
 +    for(i = 1;i < COUNT_BYTE;i++) //sectionam vectorul b
 +        index[i] = index[i-1] + count[i-1];
 +    for(i = 0; i < n; i++) { //umplem sectiunile
 +        int car = obtineOctetul(a[i],byteNr);
 +        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]); //numarul de "caractere"
 +    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;
 +}
 +</file>
  
 +<note important>Exemplul prezentat funcţionează bine pentru întregi cu acelaşi semn.</note>
 +<note tip>Performanţa de timp poate fi influenţată prin schimbarea lungimii cuvântului(k), adică prin schimbarea "bazei" folosite.</note>
 +
 +===== 4. Exercitii =====
 +
 +E0. Generaţi un vector de n întregi cu n = 1e6. Sortaţi vectorul cu cei trei algoritmi şi comparaţi rezultatele.
 +
 +===1. Shell sort===
 +
 +E1. Creaţi un alt vector(mai simplu) pentru salturi, de exemplu: {1e5,1e4,1e3,1e2,1e1,1}, unde 1ek = 10<sup>k</sup>. Încercaţi să folosiţi acest vector pentru sortare şi observaţi diferenţa de performanţă.
 +
 +===2. Heap sort===
 +
 +E2. Introduceţi o variabilă globală cu care să contorizaţi numărul de apelări ale funcţiei "cerne". Afişaţi numărul de apelări necesare pentru construirea heap-ului(makeHeap) şi numărul de apelări necesare pentru tot algoritmul(heapSort).
 +  * 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<sup>2</sup> - 1. Sortaţi vectorul în timp O(n).
 +  * Încercaţi să folosiţi altă "bază" decât 256 pentru algoritm.
 +
 +<note tip>Puteţi folosi următorul cod pentru a genera vectori de întregi de dimensiuni mari</note>
 +
 +<file cpp>
 +//MODULATOR = 2^31 - 1
 +#define MODULATOR 2147483647
 +#define MULTIP 1103515245
 +#define INCREMENT 12345
 +int seed = 0; //unsigned int pentru generat doar numere naturale
 +int rand() {
 + seed = (MULTIP * seed + INCREMENT) % MODULATOR;
 + return seed;
 +}
 +void filter(int v[], int n, int cap)
 +{
 +    for(int i = 0;i < n;i++) {
 +        v[i] = rand() % cap;
 +    }
 +}
 +</file>
 +
 +===== 5. Exerciţii de laborator (Linux) =====
 +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab9_sortari_avansate.zip|aici]]. Descărcați arhiva și dezarhivați-o. 
 +
 +=== Linux===
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
 +
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab9_sortari_avansate.zip%%''
 +  * ''%%unzip lab9_sortari_avansate.zip%%''
 +
 +Pentru compilare folositi comanda ''%%make%%''.
 +
 +=====6. Extra=====
 +
 +====6.1 qsort====
 +
 +Funcţia qsort este inclusă în **stdlib.h** şi se apelează astfel: qsort(numeVector,nrElemente,sizeof(element),functieComparare);
 +
 +<file cpp>
 +int functieComparare(const void* a,const void* b)
 +{
 +    int va = * (int *)a;
 +    int vb = * (int *)b;
 +    return va - vb;
 +}
 +//...main...
 +qsort(v, n, sizeof(int), functieComparare);
 +</file>
 +
 +====6.2 sort====
 +
 +Funcţia sort este inclusă în **algorithm** din pachetul STL şi se apelează astfel: sort(pointerStart,pointerStop,functieComparare); Valoarea de la pointerStart este prima valoare inclusă în sortare, valoarea de la pointerStop este prima valoare exclusă din sortare.
 +
 +<file cpp>
 +bool functieComparare2(int a,int b)
 +{
 +    return a <= b;
 +}
 +//...main...
 +sort(v,v + n,functieComparare2);
 +</file>
  
laboratoare/laborator-09.txt · Ultima modificare: 2017/04/27 21:18 de către iulian.matesica