Caută
• oanaunciuleanu

# Heap Sort Algorithm in C++

Heap sort is a sorting algorithm based on comparing elements in a Binary Heap data structure. We first find the maximum element and place it at the end. We repeat the same process for all the remaining elements.

```// Heap Sort

#include <iostream>
using namespace std;

void createHeap(int arrayOfNumbers[], int numberOfElements, int i)
{
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < numberOfElements && arrayOfNumbers[left] > arrayOfNumbers[largest])
{
largest = left;
}

if (right < numberOfElements && arrayOfNumbers[right] > arrayOfNumbers[largest])
{
largest = right;
}

// If largest is not the root
if (largest != i)
{
swap(arrayOfNumbers[i], arrayOfNumbers[largest]);
createHeap(arrayOfNumbers, numberOfElements, largest);
}
}

void heapSort(int arrayOfNumbers[], int numberOfElements)
{
// Build the heap
for (int i = numberOfElements / 2 - 1; i >= 0; i--)
{
createHeap(arrayOfNumbers, numberOfElements, i);
}

// Extract elements one by one
for (int i = numberOfElements - 1; i > 0; i--)
{
// Move current root to end
swap(arrayOfNumbers[0], arrayOfNumbers[i]);
createHeap(arrayOfNumbers, i, 0);
}
}

void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; ++i)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}

int main(void)
{
int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);

heapSort(arrayOfNumbers, numberOfElements);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
}```

12 afișare0 comentariu

### Postări recente

Afișează-le pe toate

#### Maximum Length Chain of Pairs in C++

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.