Heap Sort Algorithm (heap sort) implementation More...
#include <algorithm>#include <cassert>#include <iostream>
Go to the source code of this file.
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 ()Heap Sort Algorithm (heap sort) implementation
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))\)
Definition in file heap_sort.cpp.
◆ main() ◆ printArray()template<typename T>
void printArray ( T * arr, int sz )Utility function to print the array after sorting.
Definition at line 37 of file heap_sort.cpp.
37 {
38 for (int i = 0; i < sz; i++) std::cout << arr[i] << " ";
39 std::cout << "\n";
40}
◆ test()Test cases to test the program
Definition at line 99 of file heap_sort.cpp.
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]);
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]);
115 assert(std::is_sorted(arr2, arr2 + sz));
116 std::cout << "Test 2 passed\n";
117}
void heapSort(T *arr, int n)
void printArray(T *arr, int sz)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4