Introduksjon til Heap Sort in C ++

Heapsort er en av sammenligningsbaserte sorteringsteknikker og er en del av utvalgssorteringen. Hvor sortering er definert som å ordne datasett i en bestemt rekkefølge ved å bruke unik verdi kjent som et nøkkelelement i den gitte listen. Begrepet sortering ble introdusert da folk ble kjent med viktigheten av å søke i ethvert element i et gitt sett med informasjon ellers, det ville være veldig vanskelig å søke i noen post hvis den var uordnet og usortert.

Det er mange forskjellige teknikker involvert i å sortere hver med sin respektive effektivitet i tiden det tar å sortere de gitte dataene og kravet til plass i minnet. De er boble sortering, innsetting sortering, valg sortering, rask sortering, flette sortering og haug sortering.

Hva er Heap Sort?

Heapsort er en sorteringsmetode basert på den binære heapdatastrukturen som ligner på utvalgssortering der vi først oppnår det maksimale datasettet og plasserer det på slutten og fortsetter for resten av elementene.

Heapsort som navnet selv antyder. Den bygger først haugen med dataelementer fra den gitte usorterte matrisen, og deretter kontrollerer for den største varen og plasserer den på slutten av den delvis sorterte matrisen. Den gjenoppbygger igjen dyngen, søker etter den neste største platen og plasserer den i det neste tomme sporet fra slutten av halvt sortert opptak. Denne prosessen gjentas til det ikke er igjen noen gjenstander i haugen. Denne teknikken krever to matriser ett for lagring av dyngen og det andre for en sortert matrise.

Algoritme of Heap Sorter i C ++

  • Velg først rot som et forhøyet element fra det gitte informasjonssettet med elementer for å lage en maksimal haug.
  • Rekonstruer dyngen ved å plassere eller bytte roten med det siste elementet.
  • Størrelsen på dyngen vil nå krympe med 1.
  • Så lager vi igjen dyngen med gjenværende elementer og fortsetter til haugestørrelsen er redusert til 1.

Eksempel på Heap Sort i C ++

Denne teknikken bruker binær haug som er konstruert ved hjelp av et komplett binært tre der rotknuten er større enn de to barneknuter.

Vurder den gitte rekke datasett.

La oss gå i henhold til algoritmen. Det står å velge det høyeste elementet som roten og konstruere den maksimale haugen.

1. Første itterasjon

Nå vil matrisen være av formen:

Nå vil den sorterte matrisen ha formen:

Heapstørrelsen vil reduseres med 1, nå 6-1 = 5.

2. Andre itterasjon

Så nå ser bunken ut:

Matrisen er av formen:

Det sorterte arrayet vil være:

Heapstørrelsen vil bli redusert med 1, nå 5-1 = 4.

3. Tredje Iterasjon

Den nye haugen ser ut som:

Matrisen er av formen:

Det sorterte arrayet vil være:

Heapstørrelsen vil bli redusert med 1, nå 4-1 = 3.

4. Fjerde itterasjon

Den nye haugen ser ut som:

Matrisen er av formen:

Det sorterte arrayet vil være:


Heapstørrelsen vil bli redusert med 1, nå 3-1 = 2.

5. Femte gjentagelse

Den nye haugen ser ut som:

Matrisen er av formen:

Det sorterte arrayet vil være:

Heapstørrelsen vil bli redusert med 1, nå 2-1 = 1.

6. Siste gjentagelse

Den nye haugen ser ut som:

Utvalget har:

4

Fra algoritmen har vi utført alle trinnene til haugestørrelsen er 1. Så vi har nå den sorterte matrisen:


Derfor er sortert utvalg av den maksimale haugen i stigende rekkefølge. Hvis vi trenger rekkefølgen sortert i synkende rekkefølge, følg trinnene ovenfor med en minimal haug.

C ++ program for heap sortering er som gitt 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);
)

Produksjon:

Konklusjon

Heapsort er den sammenligningsbaserte teknikken som er forbedring av valg av sortering. Heap sort benytter seg av å velge det høyeste eller laveste elementet i den gitte arrayen for å sortere i henholdsvis stigende eller synkende rekkefølge med maksimal eller minimal haug. Gjennomfør denne prosessen til vi får en like stor størrelse. Denne sorteringsteknikken brukes også til å finne det største og laveste elementet i matrisen. Heap-sorteringsteknikken er mer effektiv og raskere enn utvalgssorteringsteknikken.

Anbefalte artikler

Dette er en guide til Heap Sort in C ++. Her diskuterer vi hva som er heap sort i c ++, og arbeider med algoritmen og eksempelet. Du kan også se på følgende artikler for å lære mer-

  1. Heap Sort in C
  2. Heap Sort In Java
  3. Overbelastning i C ++
  4. Pekere i C ++
  5. Overbelastning i Java

Kategori:

Programvare utvikling