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/25 18:31]
mihai.iacov [3.3 Radix Sort]
+++ laboratoare:laborator-09 [2017/02/26 22:42]
mihai.iacov [1 Obiectivele laboratorului]
@@ Linia 12: / Linia 12: @@
  *Heap-uri (pentru Heap 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.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.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=====

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină