Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-09 [2017/02/26 22:42]
mihai.iacov [1 Obiectivele laboratorului]
+++ laboratoare:laborator-09 [2017/04/27 21:18] (curent)
iulian.matesica
@@ Linia 1: / Linia 1: @@
 ====== Laborator 09: Algoritmi de sortare 2 ======
-\\
 =====1 Obiectivele laboratorului=====
@@ Linia 126: / 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.
  *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ă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 "**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 : ===
 <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>
 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>
@@ Linia 227: / Linia 281: @@
 <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>

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină