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ă

Both sides previous revision Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-09 [2017/02/27 18:17]
mihai.iacov [4. Exercitii]
laboratoare:laborator-09 [2017/04/27 18: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 283: Linia 283:
  
 ===== 4. Exercitii ===== ===== 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=== ===1. Shell sort===
Linia 299: Linia 301:
 E4. Schimbaţi funcţia de indexare(obtineOctetul) şi valoarea lui k pentru a sorta un vector de şiruri de caractere. 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).+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.   * Î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.1488219472.txt.gz · Ultima modificare: 2017/02/27 18:17 (editare externă)