retagged by
505 views

1 Answer

1 votes
1 votes

Stability in sorting algorithm means that if two items have the same value, they will occur in the same order in the sorted output as they did in the unsorted input. 

Heap sort is one such example of an unstable sorting algorithm. You can think of it this way: if we rearrange all the items of the array anyway to form new data structure (the heap), we cannot guarantee that the order of any two items remains the same. That said, any unstable sorting algorithm can in theory be made stable. You must extend the key in some way.

See example:

Heap sort unstable example

Consider array 31 19a 19b 12 11 8 7 (already in max-heap format)

here 20a = 20b just to differentiate the order we represent them as 20a and 20b

While heapsort first 31 is removed and placed in the last index then 19a is removed and placed in last but one index and 19b in the last but two index so after heap sort the array looks like

7 8 11 12 19b 19a 21.

It does not preserve the order of elements and hence can't be stable.

Quick Sort is not stable because it swaps non-adjacent elements.

Lets take an example

Given [5a, 5b, 3], the ‘5’ values will not retain their initial order.

*a and b just to show their order

Related questions

0 votes
0 votes
0 answers
2