Introducere la sortarea haldei în C ++
Heapsort este una dintre tehnicile de sortare bazate pe comparație și face parte din sortarea selecției. În cazul în care sortarea este definită ca aranjarea seturilor de date într-o ordine specifică folosind o valoare unică cunoscută ca element cheie din lista dată. Termenul de sortare a fost introdus pe măsură ce oamenii au luat cunoștință de importanța căutării oricărui element dintr-un set de informații, în caz contrar, ar fi foarte dificil să se caute vreo înregistrare dacă nu a fost comandată sau nesortată.
Există numeroase tehnici diferite pentru a sorta fiecare având eficiența lor respectivă în timpul necesar pentru a sorta datele date și cerința de spațiu în memorie. Sunt sortare de bule, sortare de inserție, sortare de selecție, sortare rapidă, sortare de îmbinare și sortare de morman.
Ce este sortarea haldei?
Heapsort este o abordare de sortare bazată pe structura binară de date heap similară sortării de selecție, unde obținem mai întâi bucata maximă de set de date și o plasăm la final și continuăm pentru restul elementelor.
Heapsort așa cum sugerează și numele. Mai întâi construiește mormântul de elemente de date din tabloul nesortat, apoi verifică elementul cel mai mare și îl plasează la sfârșitul tabloului parțial sortat. Reconstituie din nou grămada, caută următoarea cea mai mare înregistrare și o plasează în următorul slot gol de la sfârșitul aranjamentului de înregistrări pe jumătate sortat. Acest proces se repetă până când nu au mai rămas elemente în morman. Această tehnică necesită două tablouri una pentru stocarea grămadă și cealaltă pentru un tablou sortat.
Algoritmul sortării de grămadă în C ++
- Mai întâi alegeți rădăcina ca element ridicat din setul de informații date pentru a crea un maxim maxim.
- Reconstituie grămada plasând sau schimbând rădăcina cu ultimul element.
- Dimensiunea mormanului va scădea acum cu 1.
- Apoi facem din nou grămada cu elementele rămase și continuăm până când dimensiunea grămezii este redusă la 1.
Exemplu de sortare a haldei în C ++
Această tehnică folosește o grămadă binară care este construită folosind un arbore binar complet în care nodul rădăcină este mai mare decât cei doi noduri copii.
Luați în considerare setul dat de seturi de date.
Să mergem conform algoritmului. Se spune că se selectează cel mai înalt element ca rădăcină și se construiește maximul.
1. Prima iterație
Acum, tabloul va avea forma:
Acum, tabloul sortat va avea forma:
Dimensiunea mormanului va fi redusă cu 1, acum 6-1 = 5.
2. A doua iterație
Deci acum grămada arată:
Matricea are forma:
Matricea sortată va fi:
Dimensiunea mormanului va fi redusă cu 1, acum 5-1 = 4.
3. A treia iterație
Noul morman arată:
Matricea are forma:
Matricea sortată va fi:
Dimensiunea mormanului va fi redusă cu 1, acum 4-1 = 3.
4. Iratarea a patra
Noul morman arată:
Matricea are forma:
Matricea sortată va fi:
Dimensiunea mormanului va fi redusă cu 1, acum 3-1 = 2.
5. A cincea iterație
Noul morman arată:
Matricea are forma:
Matricea sortată va fi:
Dimensiunea mormanului se va reduce cu 1, acum 2-1 = 1.
6. Ultima iterație
Noul morman arată:
Matricea are:
4
Din algoritm, am efectuat toți pașii până când dimensiunea mormanului este 1. Deci avem acum tabloul sortat:
Prin urmare, tabloul sortat al masei maxime este în ordine crescătoare. Dacă avem nevoie de tablă ordonată în ordine descrescătoare, atunci urmați pașii de mai sus cu un efect minim.
Programul C ++ pentru sortarea haldelor este cel prezentat mai jos:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
ieşire:
Concluzie
Heapsort este tehnica bazată pe comparație, care este îmbunătățirea sortării selecției. Selecția de haldă folosește selectarea elementului cel mai înalt sau cel mai mic din tabloul dat pentru a sorta în ordine crescătoare sau descendentă respectiv cu cel maxim sau minim. Efectuați acest proces până când obținem unul ca mărime. Această tehnică de sortare este folosită și pentru a găsi cel mai mare și cel mai mic element din tablou. Tehnica de sortare a haldelor este mai eficientă și mai rapidă decât tehnica de sortare a selecției.
Articole recomandate
Acesta este un ghid pentru sortarea haldei în C ++. Aici vom discuta despre ce este sortarea mormanului în c ++, funcționând cu algoritmul și exemplul său. De asemenea, puteți consulta următoarele articole pentru a afla mai multe-
- Sortare pentru grămadă în C
- Sortare la grămadă în Java
- Supraîncărcare în C ++
- Punctele în C ++
- Supraîncărcare în Java