Wprowadzenie do Heap Sort w C ++

Heapsort jest jedną z technik sortowania opartą na porównaniu i jest częścią sortowania selekcyjnego. Gdzie sortowanie jest zdefiniowane jako uporządkowanie zestawów danych w określonej kolejności przy użyciu unikalnej wartości znanej jako kluczowy element na danej liście. Termin sortowania został wprowadzony, gdy ludzie poznali znaczenie przeszukiwania dowolnego elementu w danym zestawie informacji, w przeciwnym razie przeszukiwanie dowolnego rekordu byłoby bardzo trudne, gdyby był nieuporządkowany i nieposortowany.

Istnieje wiele różnych technik związanych z sortowaniem, z których każda ma odpowiednią wydajność w czasie potrzebnym do sortowania danych i zapotrzebowania na miejsce w pamięci. Są to: sortowanie bąbelkowe, sortowanie wstawiane, sortowanie selekcyjne, sortowanie szybkie, sortowanie scalone i sortowanie sterty.

Co to jest Sortowanie sterty?

Heapsort to metoda sortowania oparta na strukturze danych binarnych sterty podobna do sortowania selekcyjnego, w której najpierw uzyskujemy maksymalny kawałek zestawu danych i umieszczamy go na końcu, a następnie kontynuujemy dla pozostałych elementów.

Heapsort, jak sama nazwa wskazuje. Najpierw buduje stertę elementów danych z podanej nieposortowanej tablicy, a następnie sprawdza największy element i umieszcza go na końcu częściowo posortowanej tablicy. Ponownie odbudowuje stertę, wyszukuje następny największy rekord i umieszcza go w następnym pustym polu od końca częściowo uporządkowanego zestawu rekordów. Ten proces powtarza się, dopóki na stosie nie pozostaną żadne elementy. Ta technika wymaga dwóch tablic, jednej do przechowywania stosu, a drugiej do posortowanej tablicy.

Algorytm sortowania sterty w C ++

  • Najpierw wybierz root jako element z podwyższonego poziomu z podanego zestawu informacji, aby utworzyć maksymalną stertę.
  • Zrekonstruuj stertę, umieszczając lub zamieniając korzeń z ostatnim elementem.
  • Rozmiar sterty zmniejszy się teraz o 1.
  • Następnie ponownie tworzymy stertę z pozostałymi elementami i kontynuujemy do momentu zmniejszenia wielkości sterty do 1.

Przykład sortowania sterty w C ++

W tej technice stosuje się stertę binarną, która jest konstruowana przy użyciu pełnego drzewa binarnego, w którym węzeł główny jest większy niż dwa węzły potomne.

Rozważ podaną tablicę zestawów danych.

Chodźmy zgodnie z algorytmem. Mówi, aby wybrać najwyższy element jako root i zbudować maksymalną stertę.

1. Pierwsza iteracja

Teraz tablica będzie miała postać:

Teraz posortowana tablica będzie miała postać:

Rozmiar stosu zostanie zmniejszony o 1, teraz 6-1 = 5.

2. Druga iteracja

Więc teraz kupa wygląda następująco:

Tablica ma postać:

Posortowana tablica będzie:

Rozmiar stosu zostanie zmniejszony o 1, teraz 5-1 = 4.

3. Trzecia iteracja

Nowa kupa wygląda następująco:

Tablica ma postać:

Posortowana tablica będzie:

Rozmiar stosu zostanie zmniejszony o 1, teraz 4-1 = 3.

4. Czwarta iteracja

Nowa kupa wygląda następująco:

Tablica ma postać:

Posortowana tablica będzie:


Rozmiar stosu zostanie zmniejszony o 1, teraz 3-1 = 2.

5. Piąta iteracja

Nowa kupa wygląda następująco:

Tablica ma postać:

Posortowana tablica będzie:

Rozmiar stosu zostanie zmniejszony o 1, teraz 2-1 = 1.

6. Ostatnia iteracja

Nowa kupa wygląda następująco:

Tablica ma:

4

Z algorytmu przeprowadziliśmy wszystkie kroki, aż rozmiar sterty wyniósł 1. Mamy więc posortowaną tablicę:


Dlatego posortowana tablica maksymalnej sterty jest w porządku rosnącym. Jeśli potrzebujemy tablicy posortowanej w porządku malejącym, wykonaj powyższe kroki z minimalną stertą.

Program C ++ do sortowania stosów jest podany poniżej:

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

Wynik:

Wniosek

Heapsort to technika porównywania, która polega na ulepszeniu sortowania selekcji. Sortowanie sterty wykorzystuje wybieranie najwyższego lub najniższego elementu w danej tablicy do sortowania w kolejności rosnącej lub malejącej odpowiednio z maksymalną lub minimalną stertą. Przeprowadzaj ten proces, aż otrzymamy jeden jako rozmiar sterty. Ta technika sortowania służy również do znajdowania największego i najniższego elementu w tablicy. Technika sortowania hałd jest wydajniejsza i szybsza niż technika sortowania selekcji.

Polecane artykuły

To jest przewodnik po Heap Sort w C ++. Tutaj omawiamy, czym jest sortowanie sterty w c ++, pracując z jego algorytmem i przykładem. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej-

  1. Sortuj sterty w C.
  2. Sortuj sterty w Javie
  3. Przeciążenie w C ++
  4. Wskaźniki w C ++
  5. Przeciążenie w Javie

Kategoria:

Rozwój oprogramowania