Explain briefly

#1

why heap sort is not a stable sort please explain in example …

#2

hi @AMIT_KUMAR, let’s talk little about stable sorting .

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Stable means if the two elements have the same key, they remain in the same order or positions. But that is not the case for Heap sort.

Heap-Sort involves two steps:

  • Heap creation
  • Removing and adding the root element from heap tree into a new array which will be sorted in order

1. Order breaks during Heap Creation

Let’s say the input array is {1, 5, 2, 3, 2, 6, 2} and for the purpose of seeing the order of 2’s, say they are 2a, 2b and 2c so the array would be {1, 5, 2a, 3, 2b, 6, 2c}

Now if you create a heap (min-heap here) out of it, it’s array representation will be {1, 2b, 2a, 3, 5, 6, 2c} where order of 2a and 2b has already changed.

2. Order breaks during removal of root element

Now when we have to remove root element (1 in our case) from the heap to put it into another new array, we swap it with the last position and remove it from there, hence changing the heap into {2c, 2b, 2a, 3, 5, 6}. We repeat the same and this time we will remove ‘2c’ from the heap and put it at end of the array where we had put ‘1’.

When we finish repeating this step until the heap is empty and every element is transferred to the new array, the new array (sorted) it will look like {1, 2c, 2b, 2a, 3, 5, 6}.

Input to Heap-Sort: {1, 5, 2a, 3, 2b, 6, 2c} --> Output: {1, 2c, 2b, 2a, 3, 5, 6}

Hence we see that repeating elements (2’s) are not in same order in heap-sort

In case of any doubt feel free to ask :slight_smile:

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.