Въведение в сортирането на Heap в C ++

Heapsort е една от методите за сортиране на базата на сравнение и е част от сортирането за подбор. Когато сортирането се дефинира като подреждане на масиви от данни в някакъв конкретен ред, като се използва уникална стойност, известна като ключов елемент в дадения списък. Терминът сортиране беше въведен, тъй като хората опознаха важността на търсенето на който и да е елемент от даден набор от информация в противен случай, би било много трудно да търсят всеки запис, ако той е нередовен и несортиран.

Има много различни техники, участващи в сортирането, като всяка от тях има своята ефективност във времето, необходимо за сортиране на дадените данни и изискване за място в паметта. Те са сортиране на балончета, сортиране на вмъкване, сортиране на селекцията, бързо сортиране, сортиране на сливане и сортиране на купчина.

Какво е сортиране на купчина?

Heapsort е метод за сортиране, базиран на структурата на данни от двоични купища, подобен на сортирането на селекция, където първо получаваме максималния набор от данни и го поставяме в края и продължаваме към останалите елементи.

Heapsort, както подсказва самото име. Първо изгражда купчината от елементи от дадения несортиран масив и след това проверява за най-големия елемент и го поставя в края на частично сортирания масив. Той отново възстановява купчината, търси следващото най-голямо парче запис и го поставя в следващия празен слот от края на половината подредено подреждане на записи. Този процес се повтаря, докато в грамадата не останат никакви елементи. Тази техника изисква два масива, единият за съхраняване на купчината, а другият за сортиран масив.

Алгоритъм на купчината Сортирайте в C ++

  • Първо изберете корен като повдигнат елемент от дадения информационен набор от елементи, за да създадете максимална грамада.
  • Реконструирайте купчината, като поставите или замените корена с последния елемент.
  • Размерът на купчината сега ще се свие с 1.
  • След това отново правим купчината с останалите елементи и продължаваме, докато размерът на купчината се намали до 1.

Пример за сортиране на купчина в C ++

Тази техника използва двоична купчина, която е конструирана с помощта на цялостно бинарно дърво, където коренният възел е по-голям от двата му детски възла.

Помислете за дадения масив от набори от данни.

Нека вървим според алгоритъма. Тя казва да изберете най-високия елемент като корен и да конструирате максималната грамада.

1. Първа итерация

Сега масивът ще бъде във формата:

Сега сортираният масив ще бъде във формата:

Размерът на купчината ще бъде намален с 1, сега 6-1 = 5.

2. Втора итерация

Така че сега грамадата изглежда така:

Масивът е във формата:

Сортираният масив ще бъде:

Размерът на купчината ще бъде намален с 1, сега 5-1 = 4.

3. Трета итерация

Новата грамада изглежда така:

Масивът е във формата:

Сортираният масив ще бъде:

Размерът на купчината ще бъде намален с 1, сега 4-1 = 3.

4. Четвърта итерация

Новата грамада изглежда така:

Масивът е във формата:

Сортираният масив ще бъде:


Размерът на купчината ще бъде намален с 1, сега 3-1 = 2.

5. Пета итерация

Новата грамада изглежда така:

Масивът е във формата:

Сортираният масив ще бъде:

Размерът на купчината ще бъде намален с 1, сега 2-1 = 1.

6. Последна итерация

Новата грамада изглежда така:

Масивът има:

4

От алгоритъма сме извършили всички стъпки, докато размерът на хепата е 1. Така че сега имаме сортиран масив:


Следователно сортираният масив от максималната грамада е във възходящ ред. Ако се нуждаем от масива, сортиран в низходящ ред, след това следвайте горните стъпки с минимална купчина.

Програмата C ++ за сортиране на купчината е както е дадено по-долу:

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

изход:

заключение

Heapsort е техниката, базирана на сравнението, която е подобряването на подборното сортиране. Сортирането на Heap използва избора на най-високия или най-ниския елемент в дадения масив, за да се сортира във възходящ или низходящ ред, съответно с максимална или минимална купчина. Провеждайте този процес, докато не получим такъв като размер на купчината. Тази техника за сортиране се използва и за намиране на най-големия и най-ниския елемент в масива. Техниката за сортиране на купчина е по-ефективна и по-бърза от техниката за сортиране на селекция.

Препоръчителни статии

Това е наръчник за сортиране на Heap в C ++. Тук обсъждаме какво е сортирането на куп в c ++, като работим с неговия алгоритъм и пример. Можете също да разгледате следните статии, за да научите повече-

  1. Сортиране на купчина в С
  2. Сортиране в купа с Java
  3. Претоварване в C ++
  4. Показалци в C ++
  5. Претоварване в Java

Категория:

Разработване на софтуер