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/27 19:31] mihai.iacov [3.2 Heap 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 281: | Linia 281: | ||
<note important> | <note important> | ||
<note tip> | <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, | ||
+ | </ | ||