# C++ program to sort elements of the given array

## Program to sort elements of array

In this article we will learn how to write the program to sort elements of array. Sorting the elements of array means to arrange the elements of the array in the logical order i.e. either in ascending or descending order. There are various algorithm to sort the given array but we will use heap sort algorithm here. In this article, we will learn how we can sort the given array in C++  ## Steps to sort array elements  in C++

To sort any array into a logical order(using heap sort) following steps are followed :-

• Convert the array into heap.
• Now convert this heap into max heap.
• As the heap is converted to max heap largest element in the list is stored in the root of the heap, replace it with the last item of the heap.
• Now delete this node and reduce the size of heap by 1.
• Follow these steps until the list is sorted. ## Algorithm to sort given array elements in C++

MAX-HEAPIFY(A,i)
1- i<-left[i]
2- r<-right[i]
3- if l<heap-size[A]and A[l]>A[i]
4- then largest<-1
5- else largest<-i
6- if r<heap-size[A] and A[r]>A[largest]
7- then largest<-r
8- if largest!=i
9- then exchange A[i]<->A[largest]
10- MAX-HEAPIFY[A,largest]

HEAP-SORT(A)
1- BUILD-MAX-HEAP(A)
2- for i<-length[A] down to 2
3- do exchange A<-> heap-size[A]-1
4- heap-size[A]<-heap-size[A]-1
5- MAX-HEAPIFY(A,1)

BUILD-MAX-HEAP(A)
1- heap-size[A]<-length[A]
2- for i<-(length[A]/2) down to 1 do
3- MAX-HEAPIFY(A,i)

## C++ programming code to sort the array elements

```#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 left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

//If right child largest
if (r < n && arr[r] > arr[largest])
largest = r;

//If root is nor largest
if (largest != i)
{
swap(arr[i], arr[largest]);

//Recursively heapifying the sub-tree
heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n)
{

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

//One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
//Moving current root to end
swap(arr, arr[i]);

//Calling max heapify on the reduced heap
heapify(arr, i, 0);
}
}

//Function to print array
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << "\n";
}

int main()
{
int arr[] = {1, 14, 3, 7, 0};
int n = sizeof(arr)/sizeof(arr);
cout << "Unsorted array  \n";
display(arr, n);

heapSort(arr, n);

cout << "Sorted array  \n";
display(arr, n);
}```
```Output:
//Test case 1Unsorted array
1	14	3	7	0
Sorted array
0	1	3	7	14	//Test case 2Unsorted array 1        4     3       7       9Sorted array 1        3     4       7       9 //Test case 3Unsorted array 10        24     32       70       91Sorted array 10        24     32       70       91 //Test case 4Unsorted array 10        4     3       7       9Sorted array 3         4     7       9       10
```