Uvod u sortu gomile u C
Razvrstavanje je tehnika koja se odnosi na redoslijed elemenata na temelju različitih svojstava. (Svojstva poput uređenja podataka uzlaznim, silaznim ili abecednim redoslijedom). Jedan glavni primjer razvrstavanja o kojem ovdje možemo razmišljati je naručivanje predmeta tijekom internetske kupovine. Možemo se odnositi na cijene, popularnost, najnovije i tako dalje. Dakle, postoji mnogo tehnika za ovo pozicioniranje elemenata sortiranjem. U ovoj ćemo temi saznati više o sorti gomile u C.
Ovdje ćemo naučiti jednu od najčešćih tehnika sortiranja, Heap Sort, kroz programski jezik C.
Logika za sortu Heap
Kako zapravo možemo izvoditi hrpu vrsta? Pogledajmo u nastavku.
Prvo, gomila je jedna od struktura podataka zasnovanih na stablu. Drvo uključeno ovdje je uvijek Cjelovito binarno stablo. Postoje dvije vrste gomile
- Min - Heap: Općenito raspoređeni u uzlaznom redoslijedu, to jest ako nadređeni element čvora ima vrijednost manju od vrijednosti nadređenih elemenata čvora.
- Max - Heap: Općenito raspoređeni u silaznom redoslijedu, to jest ako nadređeni element čvora ima vrijednost više od one nadređenih elemenata čvora.
Koraci za razvrstavanje hrpe
- Jednom kada se dobiju neortirani podaci o popisu, elementi se organiziraju u strukturu podataka gomile ili na temelju stvaranja min-heap ili max-heap.
- Prvi element s gornjeg popisa dodan je u naš niz
- Ponovno se formira tehnika strukture podataka glave, kao i prvi korak, a opet se uzima i najviši ili najmanje element i dodaje se u naš niz.
- Ponovljeni koraci pomažu nam da dobijemo niz s poredanim popisom.
Program za razvrstavanje gomile u C
#include
int main()
(
int h(20), num, i, j, root, t, x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h(i));
// build max heap
for(i=0;i (
x=i;
do
(
root = (x - 1) / 2;
if (h(root) < h(x))
(
t = h(root);
h(root) = h(x);
h(x) = t;
)
x = root;
) while (x != 0);
)
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h(i));
for (j = num - 1; j >= 0; j--)
(
t = h(0);
h(0) = h(j);
h(j) = t;
root = 0;
do
(
x = 2 * root + 1;
if ((h(x) < h(x + 1)) && x < j-1)
x++;
if (h(root) (
t = h(root);
h(root) = h(x);
h(x) = t;
)
root = x;
) while (x < j);
)
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h(i));
)#include
int main()
(
int h(20), num, i, j, root, t, x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h(i));
// build max heap
for(i=0;i (
x=i;
do
(
root = (x - 1) / 2;
if (h(root) < h(x))
(
t = h(root);
h(root) = h(x);
h(x) = t;
)
x = root;
) while (x != 0);
)
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h(i));
for (j = num - 1; j >= 0; j--)
(
t = h(0);
h(0) = h(j);
h(j) = t;
root = 0;
do
(
x = 2 * root + 1;
if ((h(x) < h(x + 1)) && x < j-1)
x++;
if (h(root) (
t = h(root);
h(root) = h(x);
h(x) = t;
)
root = x;
) while (x < j);
)
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h(i));
)#include
int main()
(
int h(20), num, i, j, root, t, x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h(i));
// build max heap
for(i=0;i (
x=i;
do
(
root = (x - 1) / 2;
if (h(root) < h(x))
(
t = h(root);
h(root) = h(x);
h(x) = t;
)
x = root;
) while (x != 0);
)
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h(i));
for (j = num - 1; j >= 0; j--)
(
t = h(0);
h(0) = h(j);
h(j) = t;
root = 0;
do
(
x = 2 * root + 1;
if ((h(x) < h(x + 1)) && x < j-1)
x++;
if (h(root) (
t = h(root);
h(root) = h(x);
h(x) = t;
)
root = x;
) while (x < j);
)
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h(i));
)
Prvo tražimo od korisnika da upiše broj elemenata koji su uzeti za razvrstavanje, a zatim korisniku omogućuje unos različitih elemenata koje treba sortirati.
Slijedeći koraci
- Sljedeće na što se fokusiramo je stvaranje heap array-a, u ovom slučaju max-heap niza.
- Glavni uvjet za dobivanje max - heap niza je provjeriti da nijedna vrijednost roditeljskog čvora nije manja od njegove nadređene vrijednosti čvora. Mijenjat ćemo dok ne postignemo taj uvjet.
- Glavna prednost ovog kompletnog binarnog stabla je u tome što se lijevom i desnom podređenom čvorištu nadređenog čvora može pristupiti s vrijednostima 2 (i) + 1 i 2 * (i) + 2 vrijednosti. Gdje sam ja roditeljski čvor.
- Dakle, na taj način ovdje postavljamo svoj korijenski čvor koji sadrži maksimalnu vrijednost na krajnjem desnom mjestu čvorova lista. Zatim opet slijedi isti postupak, tako da sljedeći maksimalni broj sada postaje korijenski čvor.
- Slijedit ćemo isti postupak sve dok u nizu hrpa ne ostane samo jedan čvor.
- I tada sređujemo niz gomila kako bismo oblikovali savršeno razvrstani niz u sve većem redoslijedu.
- Napokon ispisujemo sortirani niz u izlazu.
Izlaz:
Izlaz je priložen ispod.
Dopustite da vam pokažem slikoviti prikaz događaja:
- Uneseni podaci su najprije predstavljeni u obliku jednodimenzionalnog niza kako slijedi.
- Slikovni prikaz formiranog binarnog stabla je sljedeći:
- Sada ćemo se pretvoriti u max heap, osiguravajući da su svi nadređeni čvorovi uvijek veći od podređenih čvorova. Kao što je spomenuto u izlazu pod nizom razvrstanim nizom, slikovni prikaz bio bi:
- Nakon ovoga, zamijenit ćemo korijenski čvor s ekstremnim čvorom lišća, a zatim ga izbrisati sa stabla. Čvor lišća bi bio korijen sada i opet isti postupak koji slijedi da bi ponovo dobio najviši element u korijenu
- Dakle, u ovom se slučaju sa ovog stabla briše 77 znamenki i stavljaju se u naš razvrstani niz i postupak se ponavlja.
Navedeno smo vidjeli kako formira max heap niz. Isti postupak se također bavi i formacijom nizova min. Kao što je gore spomenuto, jedina razlika je u odnosu između elemenata roditelja i podređenog čvora.
Možete li pokušati oblikovati sortu gomile prema silaznom redoslijedu?
Zaključak
Iako postoji mnogo tehnika sortiranja, sorta gomile smatra se jednom od boljih tehnika sortiranja s obzirom na vremensku i prostornu složenost. Vremenska složenost za sve najbolje, prosječne i najgore slučajeve je O (nlogn), gdje je složenost u najboljem slučaju bolja od složenosti u najgorem slučaju Quicksorta, a složenost prostora je O (1).
Preporučeni članci
Ovo je vodič za sortiranje gomile C. Ovdje raspravljamo o logici i Koraci za razvrstavanje hrpe s uzorkom koda i ishodom zajedno s slikovnim prikazima. Možete također pogledati sljedeće članke da biste saznali više -
- Poredaj u Javi
- Izbor sortiranja u Javi
- Palindrome u C programu
- Obrasci u C programiranju
- Poredaj na hrpu u C ++ (algoritam)
- Poredajte u Python
- C Programiranje množenja matrice