how is heap sort unstable?
is heap sort an online or offline sorting algorithm?
if heap sort is better in both space and time complexity than quicksort then why inbuilt libraries use randomised quicksort?
how is heap sort unstable?
is heap sort an online or offline sorting algorithm?
if heap sort is better in both space and time complexity than quicksort then why inbuilt libraries use randomised quicksort?
@Rj.25
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.
Heapsort is not stable because operations on the heap can change the relative order of equal items.
HeapSort involves two steps:
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-sorted array as they appear in the input and therefore Heap-Sort is not stable !
@Rj.25
In practice, quicksort is reliably tested to be about 2–3 times as fast as heapsort (because of its cache efficiency and smoother memory access pattern), and it is also more memory efficient.
Then there is the worry that quicksort has bad worst-case performance. To address this, the sorting algorithm in most languages’ standard libraries is actually a hybrid of quicksort with some other algorithm that kicks in when the performance turns out bad. Because of that, the worst case performance of the hybrid algorithm is improved to O(nlogn), like heapsort.
@Rj.25 Heapsort will first take the entire array and convert it into a max heap, so its an offline algorithm