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 Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-09 [2017/02/25 18:00] mihai.iacov [3.3 Radix Sort] |
laboratoare:laborator-09 [2017/02/26 22:42] mihai.iacov [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 144: | Linia 184: | ||
===Implementare: | ===Implementare: | ||
+ | Exemplul prezentat foloseşte un octet pe post de " | ||
<file cpp> | <file cpp> | ||
+ | #define BYTE 8 | ||
+ | #define COUNT_BYTE 256 | ||
int obtineOctetul(int n,int byteNr) | int obtineOctetul(int n,int byteNr) | ||
{ // | { // | ||
Linia 168: | Linia 211: | ||
b[index[car]++] = a[i]; | b[index[car]++] = a[i]; | ||
} | } | ||
- | afisare(b, | ||
} | } | ||
void radixSort(int *a,int n) | void radixSort(int *a,int n) | ||
Linia 182: | Linia 224: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | <note important> | ||
+ | <note tip> | ||