Johdanto kasalajitteluun C ++: ssa

Heapsort on yksi vertailupohjaisista lajittelutekniikoista ja on osa valintalajittelua. Missä lajittelu määritellään tietojoukkojen järjestämiseksi tietyssä järjestyksessä käyttämällä ainutlaatuista arvoa, joka tunnetaan avainelementtinä annetussa luettelossa. Lajittelu-termi otettiin käyttöön, kun ihmiset tutustuivat minkä tahansa tietyn tietojoukon elementtien etsimisen tärkeyteen. Muuten tietueesta olisi erittäin vaikea hakea, jos se on järjestämätön ja lajittelematon.

Kummankin lajitteluun liittyy monia erilaisia ​​tekniikoita, joilla on vastaava tehokkuus tietyn datan ja muistin tilan tarvetta lajittelemiseen kuluessa. Ne ovat kuplalajittelu, lisäyslajittelu, valintalaji, nopea lajittelu, yhdistämislajittelu ja kasalajittelu.

Mikä on Heap Sort?

Heapsort on lajittelumenetelmä, joka perustuu binäärisen kasan tietorakenteeseen, joka on samanlainen kuin valintalajittelu, jossa ensin saadaan suurin mahdollinen tietojoukko ja sijoitetaan se loppuun ja jatketaan loput elementit.

Heapsort, kuten nimi itse viittaa. Se rakentaa ensin kasa dataelementtejä annetusta lajittelemattomasta taulukosta ja tarkistaa sitten suurimman alkion ja sijoittaa sen osittain lajitellun taulukon loppuun. Se jälleenrakentaa kasan, etsii seuraavan suurimman levytyksen ja sijoittaa sen seuraavaan tyhjään paikkaan puoliksi lajiteltujen levyjen järjestelyn lopusta. Prosessi toistetaan, kunnes kasaan ei jää mitään esineitä. Tämä tekniikka vaatii kaksi taulukkoa yhden kasan varastoimiseksi ja toisen lajiteltua ryhmää varten.

Kasan algoritmi Lajittele C ++: ssa

  • Valitse ensin juuri juuri korotettuna elementtinä annetusta tietoelementistä, jotta saadaan aikaan maksimaalinen kasa.
  • Uudelleenrakentaa kasa asettamalla tai vaihtamalla juuri juuri viimeisen elementin kanssa.
  • Kasan koko pienenee nyt yhdellä.
  • Sitten teemme taas kasan jäljellä olevilla elementeillä ja jatkamme, kunnes kasan koko pienenee arvoon 1.

Esimerkki kasalajittelu C ++: ssa

Tämä tekniikka käyttää binaarikasoa, joka on rakennettu käyttämällä kokonaista binaaripuuta, jossa juurisolmu on suurempi kuin sen kaksi lastesolmua.

Harkitse annettua joukkoa tietojoukkoja.

Mennään algoritmin mukaan. Se sanoo, että valitaan juuri ylin elementti ja rakennetaan suurin mahdollinen kasa.

1. Ensimmäinen toisto

Nyt taulukko on muodossa:

Nyt lajiteltu taulukko on muodossa:

Kasan koko pienenee yhdellä, nyt 6-1 = 5.

2. Toinen toisto

Joten nyt kasa näyttää seuraavalta:

Matriisi on seuraavan muotoinen:

Lajiteltu taulukko on:

Kasan koko pienenee yhdellä, nyt 5-1 = 4.

3. Kolmas toisto

Uusi kasa näyttää seuraavalta:

Matriisi on seuraavan muotoinen:

Lajiteltu taulukko on:

Kasan koko pienenee yhdellä, nyt 4-1 = 3.

4. Neljäs toisto

Uusi kasa näyttää seuraavalta:

Matriisi on seuraavan muotoinen:

Lajiteltu taulukko on:


Kasan koko pienenee yhdellä, nyt 3-1 = 2.

5. Viides toisto

Uusi kasa näyttää seuraavalta:

Matriisi on seuraavan muotoinen:

Lajiteltu taulukko on:

Kasan koko pienenee yhdellä, nyt 2-1 = 1.

6. Viimeinen toisto

Uusi kasa näyttää seuraavalta:

Ryhmässä on:

4

Algoritmista olemme suorittaneet kaikki vaiheet, kunnes kasan koko on 1. Joten meillä on nyt lajiteltu taulukko:


Siksi maksimaalisen kasan lajiteltu ryhmä on nousevassa järjestyksessä. Jos tarvitsemme laskevassa järjestyksessä lajiteltua taulukkoa, noudata yllä olevia vaiheita pienellä kasalla.

C ++ -ohjelma kasaan lajitteluun on esitetty alla:

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

lähtö:

johtopäätös

Heapsort on vertailupohjainen tekniikka, joka on parannus valintalajitteluun. Kasalajittelu hyödyntää tietyn ryhmän korkeimman tai alimman elementin valitsemista lajitellaan nousevassa tai laskevassa järjestyksessä vastaavasti maksimaalisen tai pienen kasan kanssa. Suorita tätä prosessia, kunnes saamme yhden kasan kokoisena. Tätä lajittelutekniikkaa käytetään myös taulukon suurimman ja alimman elementin löytämiseen. Kasalajittelu tekniikka on tehokkaampaa ja nopeampaa kuin valintalajittelu tekniikka.

Suositellut artikkelit

Tämä on opas Heap Sort C ++ -sovellukseen. Tässä keskustellaan siitä, mikä on kasalajittelu c ++: ssa, algoritmin ja esimerkin kanssa. Voit myös katsoa seuraavia artikkeleita saadaksesi lisätietoja-

  1. Kasa Lajittele C: ssä
  2. Kasa lajittelu Java
  3. Ylikuormitus C ++: ssa
  4. Osoittimet C ++: ssa
  5. Ylikuormitus Java-sovelluksessa

Luokka:

Ohjelmistokehitys