Heapsort The array A stores eight integer numbers in this order: 5,2,3,7,22,15,6

Question

Heapsort

The array A stores eight integer numbers in this order: 5,2,3,7,22,15,6,10. Simulate HEAP-SORT on this input. Stop when heap-size is set to 4. Give a snapshot of the contents of A at this point in the execution, and then explain the running time of Heapsort.

Sorting

For each of the following sorting algorithms QuickSort, CountingSort and RadixSort answer the following questions:
(a) What is its woret-case time performance on an input of n keys?
(b) Is it sable?
(c) Does it sort in place?

Explanation / Answer

First we will make the heap from the given array

Then after each step, array will look like

Time complexity of heap sort is O(nlogn), it is because the complexity of heapify process is O(logn) and it is done n times.

Quick Sort O(n^2), Not Stable, In place

Conting Sort O(n+k), Stable, Not in place

Radix Sort O(w*n), Stable, Not in place

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.