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 | ||
laboratoare:laborator-09 [2017/02/24 22:18] mihai.iacov [3.3 Radix Sort] |
laboratoare:laborator-09 [2017/04/27 21:18] (curent) 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: | ||
| | ||
| | ||
- | *deplasarea | + | *operaţii |
- | | + | |
=====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 " | ||
+ | * 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 | + | 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 | ||
+ | |||
+ | 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. Algoritmii===== | ||
Linia 86: | Linia 126: | ||
| | ||
*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): | ||
+ | | ||
+ | * 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 : === | === 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; //" | ||
+ | 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 < | #include < | ||
void heapSort(int a[], int n) //fara vector din STL | void heapSort(int a[], int n) //fara vector din STL | ||
{ | { | ||
- | make_heap(a, | + | make_heap(a, |
- | sort_heap(a, | + | sort_heap(a, |
} | } | ||
</ | </ | ||
Linia 122: | Linia 216: | ||
* timp mediu: O(N * k) | * timp mediu: O(N * k) | ||
* timp la limită: O(N * k) | * timp la limită: O(N * k) | ||
- | * memorie: O(N) | + | * memorie: O(N + k) |
* Stabil: DA | * Stabil: DA | ||
k = lungimea cuvântului/ | 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 ===== | ||
+ | |||
+ | 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, | ||
+ | |||
+ | ===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< | ||
+ | * Încercaţi să folosiţi altă " | ||
+ | |||
+ | <note tip> | ||
+ | |||
+ | <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; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== 5. Exerciţii de laborator (Linux) ===== | ||
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | =====6. Extra===== | ||
+ | |||
+ | ====6.1 qsort==== | ||
+ | |||
+ | Funcţia qsort este inclusă în **stdlib.h** şi se apelează astfel: qsort(numeVector, | ||
+ | |||
+ | <file cpp> | ||
+ | int functieComparare(const void* a,const void* b) | ||
+ | { | ||
+ | int va = * (int *)a; | ||
+ | int vb = * (int *)b; | ||
+ | return va - vb; | ||
+ | } | ||
+ | // | ||
+ | qsort(v, n, sizeof(int), | ||
+ | </ | ||
+ | |||
+ | ====6.2 sort==== | ||
+ | |||
+ | Funcţia sort este inclusă în **algorithm** din pachetul STL şi se apelează astfel: sort(pointerStart, | ||
+ | |||
+ | <file cpp> | ||
+ | bool functieComparare2(int a,int b) | ||
+ | { | ||
+ | return a <= b; | ||
+ | } | ||
+ | // | ||
+ | sort(v,v + n, | ||
+ | </ | ||
+ |