Adaptive heap sort: Difference between revisions

Revision as of 01:13, 17 October 2022

Revision as of 01:17, 17 October 2022

Line 9:

# Repeat Step 2 and 3 until the heap has only one element. Put this last element at the end of the list and output the list. The data in the list will be sorted.

Below is a C/C++ implementation that builds up a Max-Heap and sorts the array after the heap is built.

<syntaxhighlight lang="c++">

#include <iostream>

/*

A C/C++ sample heap sort code that sort an array to an increasing order

*/

using namespace std;

void heapify(int array[], int start, int end); // A function that build up a max-heap binary tree

void heapify(int array[], int start, int end); // A function that build up a max-heap binary tree

void heapify(int array[], int start, int end)

{

Line 25 ⟶ 22:

int child = parent * 2 + 1;

while (child <= end)

{ if (child + 1 <= end ) // when there are two child nodes

{

if (array[child + 1] > array[child])

Line 47 ⟶ 44:

}

void heap_sort (int array[], int len); // heap_sort function

void heap_sort (int array[], int len)

{

Line 61 ⟶ 57:

}

}

int main()

{

int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1}; //the array that will be sorted

//the array that will be sorted

int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1}; //the array that will be sorted

int array_len = sizeof(array)/sizeof(*array); //length of the array

heap_sort (array, array_len);// heap sort

return 0;

}