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 19:12] mihai.iacov [2.3 Bit Shift] |
laboratoare:laborator-09 [2017/02/27 17:31] mihai.iacov [3.2 Heap Sort] |
||
---|---|---|---|
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++ : | Menţionăm următoarele operaţii pe biţi ce se pot folosi în C/C++ : | ||
Linia 110: | Linia 126: | ||
| | ||
*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. | *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): | ||
+ | | ||
+ | | ||
+ | * 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. 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 în | ||
=== Implementare : === | === Implementare : === |