Introduktion til Heap Sort i C ++
Heapsort er en af de sammenligningsbaserede sorteringsteknikker og er en del af markeringen. Hvor sortering defineres som arrangering af datasæt i en bestemt rækkefølge ved hjælp af unik værdi kendt som et nøgleelement i den givne liste. Udtrykket sortering blev introduceret, da folk fik kendskab til vigtigheden af at søge efter ethvert element i et givet sæt information ellers ville det være meget vanskeligt at søge i nogen post, hvis den var uordnet og usorteret.
Der er mange forskellige teknikker involveret i sortering af hver med deres respektive effektivitet i den tid det tager at sortere de givne data og behovet for plads i hukommelsen. De er boble sortering, indsættelsessortering, udvælgelsessortering, hurtig sortering, sammenfletningssortering og heapsortering.
Hvad er Heap Sort?
Heapsort er en sorteringsmetode, der er baseret på den binære heap-datastruktur, der ligner udvælgelsessortering, hvor vi først får det maksimale stykke datasæt og placerer det i slutningen og fortsætter til resten af elementerne.
Heapsort som navnet selv antyder. Den bygger først bunken med dataelementer fra den givne usorterede matrix og kontrollerer derefter for den største vare og placerer den i slutningen af den delvist sorterede matrix. Den genopbygger igen dyngen, søger efter det næste største stykke plade og placerer den i det næste tomme slot fra slutningen af det halvsorterede arrangement af poster. Denne proces gentages, indtil der ikke er nogen poster tilbage i dyngen. Denne teknik kræver to matriser, den ene til opbevaring af dyngen og den anden til en sorteret matrix.
Algoritme of Heap Sorter i C ++
- Vælg først rod som et forhøjet element fra det givne informationssæt med elementer for at skabe en maksimal bunke.
- Rekonstruer dyngen ved at placere eller udskifte roden med det sidste element.
- Højestørrelsen vil nu krympe med 1.
- Derefter laver vi igen dyngen med de resterende elementer og fortsætter, indtil dyngen er reduceret til 1.
Eksempel på Heap Sort i C ++
Denne teknik bruger binær bunke, der er konstrueret ved hjælp af et komplet binært træ, hvor rodnoden er større end dens to børneknuder.
Overvej den givne række datasæt.
Lad os gå efter algoritmen. Det siger at vælge det højeste element som rod og konstruere den maksimale bunke.
1. Første gentagelse
Nu vil matrixen være af formen:
Nu er den sorterede matrix af formen:
Heapstørrelsen reduceres med 1, nu 6-1 = 5.
2. Anden Iteration
Så nu ser bunken ud:
Arrayet har formen:
Det sorterede array vil være:
Heapstørrelsen reduceres med 1, nu 5-1 = 4.
3. Tredje gentagelse
Den nye bunke ser ud som:
Arrayet har formen:
Det sorterede array vil være:
Heapstørrelsen reduceres med 1, nu 4-1 = 3.
4. Fjerde gentagelse
Den nye bunke ser ud som:
Arrayet har formen:
Det sorterede array vil være:
Heapstørrelsen reduceres med 1, nu 3-1 = 2.
5. Femte gentagelse
Den nye bunke ser ud som:
Arrayet har formen:
Det sorterede array vil være:
Heapstørrelsen reduceres med 1, nu 2-1 = 1.
6. Sidste gentagelse
Den nye bunke ser ud som:
Arrayet har:
4
Fra algoritmen har vi udført alle trin, indtil bunkestørrelsen er 1. Så vi har nu det sorterede array:
Derfor er den sorterede række af den maksimale bunke i stigende rækkefølge. Hvis vi har brug for matrixen sorteret i faldende rækkefølge, skal du følge ovenstående trin med en minimal bunke.
C ++ program til heap sortering er som angivet nedenfor:
#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);
)
Produktion:
Konklusion
Heapsort er den sammenligningsbaserede teknik, der er forbedringen af valg af sortering. Heap sortering gør brug af at vælge det højeste eller laveste element i den givne matrix for at sortere i henholdsvis stigende eller faldende rækkefølge med den maksimale eller minimale bunke. Udfør denne proces, indtil vi får en som bunke størrelse. Denne sorteringsteknik bruges også til at finde det største og laveste element i matrixen. Heapsorteringsteknikken er mere effektiv og hurtigere end udvælgelsessorteringsteknikken.
Anbefalede artikler
Dette er en guide til Heap Sort i C ++. Her diskuterer vi, hvad der er heap-sortering i c ++, og arbejder med dets algoritme og eksempel. Du kan også se på de følgende artikler for at lære mere-
- Heap Sort in C
- Heap sortering i Java
- Overbelastning i C ++
- Pegere i C ++
- Overbelastning i Java