Sissejuhatus hunnikute sortimisse C ++

Heapsort on üks võrdluspõhiseid sorteerimistehnikaid ja on osa valiku sortimisest. Kui sortimine on määratletud kui andmekogumite järjestamine mingis kindlas järjekorras, kasutades unikaalset väärtust, mida nimetatakse antud loendis võtmeelemendiks. Sorteerimise mõiste kehtestati, kuna inimesed said teada, kui oluline on mis tahes teabekomplekti elemendist otsida, vastasel korral oleks väga keeruline leida kirjet, kui see oleks järjestamata ja sortimata.

Sorteerimisega on seotud palju erinevaid tehnikaid, millel kõigil on oma tõhusus antud andmete ja mäluruumi vajaliku sorteerimiseks kuluva aja jooksul. Need on mullide sorteerimine, sisestamise sorteerimine, sorteerimise sorteerimine, kiire sortimine, liitmine ja hunnikute sortimine.

Mis on Heap Sort?

Heapsort on sorteerimismeetod, mis põhineb binaarse hunniku andmestruktuuril, mis sarnaneb valiku sortimisega, kus kõigepealt saame maksimaalse andmekogumi ja asetame selle lõppu ning jätkame ülejäänud elementidega.

Heapsort, nagu nimigi viitab. Kõigepealt ehitatakse antud sortimata massiivist hunnik andmeelemente ja seejärel kontrollitakse suurimat üksust ning paigutatakse see osaliselt sorteeritud massiivi lõppu. See ehitab uuesti hunniku üles, otsib üles järgmise suurima plaadi ja asetab selle järgmisesse tühja pessa plaatide poolest sorteeritud paigutuse lõpust. Seda protseduuri korratakse seni, kuni hunnikusse pole ühtegi eset jäänud. See tehnika nõuab kahte massiivi - ühte hunniku hoidmiseks ja teist sorteeritud massiivi jaoks.

Hunniku algoritm Sorteeri C ++

  • Esiteks valige antud elemenditeabekomplektist kõrgendatud elemendina juur, et luua maksimaalne hunnik.
  • Rekonstrueerige hunnik, asetades või vahetades juure viimase elemendiga.
  • Nüüd väheneb hunniku suurus ühe võrra.
  • Siis teeme jälle hunniku allesjäänud elementidega ja jätkame, kuni hunniku suurus on vähendatud 1-ni.

Näide hunnikust: C ++

See meetod kasutab binaarset hunnikut, mis on konstrueeritud täieliku binaarse puu abil, kus juursõlm on suurem kui selle kahes lapsesõlmes.

Mõelge antud andmekogumite massiivile.

Lähme vastavalt algoritmile. Ta ütleb, et vali juureks kõrgeim element ja konstrueerib maksimaalse hunniku.

1. Esimene kordamine

Nüüd on massiiv järgmine:

Nüüd on sorteeritud massiiv järgmisel kujul:

Hunniku suurust vähendatakse ühe võrra, nüüd 6-1 = 5.

2. Teine kordamine

Nüüd näeb hunnik välja selline:

Massiiv on kujul:

Sorteeritud massiiv on järgmine:

Hunniku suurust vähendatakse ühe võrra, nüüd 5-1 = 4.

3. Kolmas kordamine

Uus hunnik näeb välja selline:

Massiiv on kujul:

Sorteeritud massiiv on järgmine:

Hunniku suurust vähendatakse ühe võrra, nüüd 4-1 = 3.

4. Neljas kordus

Uus hunnik näeb välja selline:

Massiiv on kujul:

Sorteeritud massiiv on järgmine:


Hunniku suurust vähendatakse ühe võrra, nüüd 3-1 = 2.

5. Viies kordamine

Uus hunnik näeb välja selline:

Massiiv on kujul:

Sorteeritud massiiv on järgmine:

Hunniku suurust vähendatakse ühe võrra, nüüd 2-1 = 1.

6. Viimane kordamine

Uus hunnik näeb välja selline:

Massiivil on:

4

Algoritmist alates oleme kõik toimingud läbi viinud, kuni hunniku suurus on 1. Nii et nüüd on meil sorteeritud massiiv:


Seetõttu on maksimaalse hunniku sorteeritud massiiv kasvavas järjekorras. Kui meil on vaja massiivi kahanevas järjekorras sortida, siis järgige ülaltoodud samme minimaalse hunnikuga.

C ++ programm hunnikute sortimiseks on järgmine:

#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);
)

Väljund:

Järeldus

Heapsort on võrdlusel põhinev tehnika, mis täiustab sorteerimist. Hunnikute sortimine kasutab antud massiivi kõrgeima või madalaima elemendi valimist, et sortida vastavalt kasvavas või kahanevas järjekorras maksimaalse või minimaalse hunnikuga. Viige seda protsessi läbi, kuni saame ühe hunniku suuruseks. Seda sorteerimistehnikat kasutatakse ka massiivi suurima ja madalaima elemendi leidmiseks. Hunnikute sorteerimistehnika on tõhusam ja kiirem kui sorteerimistehnika.

Soovitatavad artiklid

See on C ++-s Heap Sortimise juhend. Siin arutame, mis on c ++-s hunnikusorteerimine, töötades koos selle algoritmi ja näitega. Lisateabe saamiseks võite vaadata ka järgmisi artikleid -

  1. Hunnik Sorteeri C-s
  2. Hunnik sorteerib Java
  3. C ++ ülekoormus
  4. C ++ osutid
  5. Ülekoormus Java-s

Kategooria:

Tarkvaraarendus