Heap Sort In C++

We use recursion to perform heap sort, firstly we heapify to create a min or max Heap to perform Descending or Ascending order of sorting, depending on the requirement.

In this article we are going to sort the given array in ascending order, so we have to perform max heapify operation. Once that is done we swap the current index element with the top element, and repeat the process until the entire array is sorted.

Time Complexity of Heap Sort is O( Log(n) ).

Code For Heap Sort In C++

#include<iostream>

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<n && arr[l] > arr[largest])

         largest = l;

        if(r<n && arr[r] > arr[largest])

         largest = r;

        if(largest != i)

        {

                swap(arr[i] , arr[largest]);

                heapify(arr , n , largest);

        }

}

// void heapify...

void HeapSort(int arr[] , int n)

{

        for(int i = n / 2  - 1 ; i <= n ; i++)

        {

                heapify( arr , n , i );

        }

        for(int i = n - 1 ; i >= 0 ; i--)

        {

                swap( arr[0] , arr[i]);

                heapify(arr , i , 0);

        }

}

// void HeapSort...

void showArr(int arr[] , int size)

{

        for(int i = 0 ; i < size; i++)

        {

                cout<< arr[i] << " ";

        }

cout<<endl;

}

// void showArr...

int main()

{

       int arr[] = {3 , 4 , 5 , 2 , 1 , 6 };

       int size = sizeof(arr) / sizeof(*arr);

        HeapSort(arr,size);

        showArr( arr , size );

return 0;

}

// int main...

Output for Heap Sort In C++

1  2  3  4  5  6

Iterative Merge Sort in C++

The Merge Sort that we've seen before in this blog was a recursive merge sort, but what if you were asked to implement merge sort using iteration. Well, we can implement iterative merge sort very easily using only 2 loops

.

Time Complexity Of Iterative Merge Sort

Time Complexity of iterative merge sort is  O(nLog(n)).

Code For Iterative Merge Sort In C++

#include<iostream>

using namespace std;

#define size 20

void Merge(int arr[] , int low, int mid, int high)

{

        int tempArr[size], tempPos,i,j;

        

        i=tempPos=low;

        j=high;

        while(i<=mid && j <= High)

        {

                if(arr[i] < arr[j])

                {

                        tempArr[tempPos++]=arr[i++];

                }

                else

                {

                        tempArr[tempPos++]=arr[j++];

                }

        }

if(i > mid)

{

        for( int k = j ; k <= high ; k++)

        {

                tempArr[tempPos++] = arr[k];

        }

}

else

{

      for( int k = i ; k <= mid ; k++)

        {

                tempArr[tempPos++] = arr[k];

        }

}

for(int p = low ; p <= high ; p++)

{

    arr[p] = tempArr[p];

}

}

//void merge...

void iterativeMergeSort(int arr[], int n)

{

        int p,i,l,m,h;

        

        for( p = 2 ; p <= n ; p *= 2)

        {

                for( i = 0 ; i + p - 1 <= n ; i += p)

                {

                    l = i;

                    h = i + p + 1;

                    m = ( l + h) / 2;

                    Merge( arr , l , m , h);

                }

        }

    if( p / 2 < n)

    {

            Merge( arr , 0 , p / 2 - 1 , n);

    }

}

// void iterativeMergeSort...

void showArr( int arr[] , int n)

{

        for( int i = 0 ;i < n; i++)

        {

                cout<<arr[i]<<" ";

        }

cout<<endl;

}

// void showArr...

int main()

{

      int arr[] = {3 , 4 , 2 , 5 , 6 , 7 , 1 , 9 , 8};

      int s = sizeof( arr ) / sizeof( *arr );

       

       iterativeMergeSort( arr , s );

       showArr(arr,s);

return 0;

}

//int main...

Output of Iterative Merge Sort Code 

1  2  3  4  5  6  7  8  9