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++

Sort the given array

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.
C++ program to sort the given array

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[1]<-> 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[0], 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[0]);
    cout << "Unsorted array  \n";
    display(arr, n);
    
    heapSort(arr, n);
 
    cout << "Sorted array  \n";
    display(arr, n);
}
Output:
//Test case 1
Unsorted array 1 14 3 7 0 Sorted array 0 1 3 7 14
//Test case 2
Unsorted array
1 4 3 7 9
Sorted array
1 3 4 7 9

//Test case 3
Unsorted array
10 24 32 70 91
Sorted array
10 24 32 70 91

//Test case 4
Unsorted array
10 4 3 7 9
Sorted array
3 4 7 9 10