Question

Sort 22, 78, 10, 56, 12, 7, 34, 56 in ascending order using the Heapsort. Also learn to write the algorithm and pseudocode.

Answer 1

Heapsort is a comparison-based sorting algorithm using a binary heap data structure. In ascending order, sorting the array [22, 78, 10, 56, 12, 7, 34, 56] using Heapsort results in [7, 10, 12, 22, 34, 56, 56, 78].

Step-by-step explanation:

Heapsort Algorithm

The Heapsort algorithm is a comparison-based sorting technique based on a binary heap data structure. It's similar to the selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.

Heapsort Steps

1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
3. Repeat the above steps while size of heap is greater than 1.

Pseudocode

algorithm heapsort(A)
build_max_heap(A)
for i = A.length downto 2
swap A[1] with A[i]
heap_size = heap_size - 1
max_heapify(A, 1)
end algorithm