Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
heap_sort.cpp File Reference

Heap Sort Algorithm (heap sort) implementation More...

#include <algorithm>
#include <cassert>
#include <iostream>
Include dependency graph for heap_sort.cpp:

Functions

template<typename T >
void printArray (T *arr, int sz)
 
template<typename T >
void heapify (T *arr, int n, int i)
 
template<typename T >
void heapSort (T *arr, int n)
 
void test ()
 
int main ()
 

Detailed Description

Heap Sort Algorithm (heap sort) implementation

Author
Ayaan Khan

Heap-sort is a comparison-based sorting algorithm. Heap-sort can be thought of as an improved selection sort: like selection sort, heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heap sort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

Time Complexity - \(O(n \log(n))\)

Function Documentation

◆ main()

int main ( void  )

Main function

120  {
121  test();
122  return 0;
123 }
Here is the call graph for this function:

◆ printArray()

template<typename T >
void printArray ( T *  arr,
int  sz 
)

Utility function to print the array after sorting.

Parameters
arrarray to be printed
szsize of array
37  {
38  for (int i = 0; i < sz; i++) std::cout << arr[i] << " ";
39  std::cout << "\n";
40 }

◆ test()

void test ( )

Test cases to test the program

99  {
100  std::cout << "Test 1\n";
101  int arr[] = {-10, 78, -1, -6, 7, 4, 94, 5, 99, 0};
102  int sz = sizeof(arr) / sizeof(arr[0]); // sz - size of array
103  printArray(arr, sz); // displaying the array before sorting
104  heapSort(arr, sz); // calling heapsort to sort the array
105  printArray(arr, sz); // display array after sorting
106  assert(std::is_sorted(arr, arr + sz));
107  std::cout << "Test 1 Passed\n========================\n";
108 
109  std::cout << "Test 2\n";
110  double arr2[] = {4.5, -3.6, 7.6, 0, 12.9};
111  sz = sizeof(arr2) / sizeof(arr2[0]);
112  printArray(arr2, sz);
113  heapSort(arr2, sz);
114  printArray(arr2, sz);
115  assert(std::is_sorted(arr2, arr2 + sz));
116  std::cout << "Test 2 passed\n";
117 }
Here is the call graph for this function:
heapSort
void heapSort(T *arr, int n)
Definition: heap_sort.cpp:84
test
void test()
Definition: heap_sort.cpp:99
std::is_sorted
T is_sorted(T... args)
std::cout
printArray
void printArray(T *arr, int sz)
Definition: heap_sort.cpp:37