Question

1.give an example and demonstrate that heapsort is not a stable sorting algorithm, 2.discuss why heapsort is unstable

Answer 1

1.Ans-:

votes
up vote
2
down vote
accepted
Here i am representing an example of Stable Sort: A sort which doesn't change the relative position of same/equal elements.

For example,
I/P: 2, 4, 3(a), 5, 1, 3(b)
O/P: 1, 2, 3(a), 3(b), 4, 5

In I/P 3(b) comes after 3(a) and the same stays intact in the O/P.

Let us take the following example to explain the above :

3,3,2,1
we consider the first 3 to be 3(a) and second 3 to be 3(b).

3(a),3(b),2,1

Heapsort begins by extracting the maximum number from the max-heap, which is the first element and then putting it on the last position.

Example -:

3(b),2,1,3(a)

Then size is decreased by 1 and a heapify operation is applied.Therefore the new size is 3 and the first three elements already satisfy the heap property.

Now the next step which show that heapsort is not stable.

Again we will extract the maximum from the heap which is the first element and put it in last position.

But because size is now 3, the last position is left of 3(a) and hence we get:
like-:

2,1,3(b),3(a)

As we can see that order of the elements 3(a) and 3(b) is reversed from the original order and remaining part of the heapsort will only sort the first two elements and therefore, the elements 3(a) and 3(b) will remain intact at their positions. This is the reason that heapsort is not stable.

The final result is

1,2,3(b),3(a) which changes the relative order of elements.

2.Ans-:

. Heapsort is unstable sort because It might rearrange the relative order of items that have the same key and differ it in the way they are present in initial array .

As seen in the above example The final sequence of the results from heapsort comes from removing items from the created heap based on the key field .Any information about the ordering of the items in the original sequence was lost during the heap creation stage, which came first.