In Java Heap sort seems a best sorting algorithm while sorting an array of random numbers according to http://www.sorting-algorithms.com/ But still I read that Heap sort is not stable, why so? Which sorting algorithm should be considered best algorithm while sorting an array or random numbers?
Asked
Active
Viewed 5,538 times
1
-
6Do you know what "stable" means in context of sorting algorithms? – Sirko Aug 04 '15 at 09:16
-
2I don't see how you arrived at the conclusion that heap sort is the best one. It is known to perform less well than QuickSort because it isn't cache-friendly (it jumps all over the array while sorting). BTW QuickSort is another _unstable_ sort algorithm, which is why it is only used to sort primitive arrays in Java. – Marko Topolnik Aug 04 '15 at 09:19
-
we cant say any algorithm is best for all purpose.It depends on the operation. – Spartan Aug 04 '15 at 09:20
-
@Sirko No I really don't know what "stable" means in context of sorting algorithms. – Prakhar Jain Aug 04 '15 at 09:23
-
@thanga the specific operation you refer to in this case is sorting an array of random numbers. – Gimby Aug 04 '15 at 09:23
-
Try sorting an array with some sample numbers using heap sort.. also keep a repeating element, marked as `a` and `b`. You will get to know. – Haris Aug 04 '15 at 09:23
-
@MarkoTopolnik This site http://www.sorting-algorithms.com shows nice visuals on complexity of different sorting algorithms. – Prakhar Jain Aug 04 '15 at 09:25
-
@thanga My question is which one should be the best to sort an array of random numbers, Numbers includes decimal numbers also. – Prakhar Jain Aug 04 '15 at 09:26
-
Yes, I know about the site, but 1) typical-case complexity of HeapSort is on a par with QuickSort and 2) the fixed costs are larger for HeapSort on any modern piece of hardware. – Marko Topolnik Aug 04 '15 at 09:28
-
http://programmers.stackexchange.com/questions/220241/sorting-an-array-of-numbers-with-decimal-places – Spartan Aug 04 '15 at 09:33
-
1There is no such thing as "best". There are better and worse ones for different scenarios. Quicksort is usually better than most for example, but I wouldn't want to use it when I need to sort data on disk. There are also non-comparison sorts, which can be blindingly fast but their applicability is limited. – biziclop Aug 04 '15 at 09:34
-
1So the occult meaning pf your question is 'what does "stable" mean in sorting', and the best answer to that is to look it up. – user207421 Aug 04 '15 at 09:47
-
@PrakharJain Hope this explains it well. – Sumeet Aug 04 '15 at 11:54
-
@PrakharJain Feel free for any queries. – Sumeet Aug 04 '15 at 12:40
-
See http://stackoverflow.com/a/8312128/56778 – Jim Mischel Aug 04 '15 at 14:59
-
@Sumeet Thanks Sumeet. – Prakhar Jain Aug 05 '15 at 09:40
-
@PrakharJain You forgot to accept. – Sumeet Aug 05 '15 at 11:39
3 Answers
2
Because it does not guarantee that when it encounters 2 equal elements in the collection that is being sorted, that their position will be preserved.
Let's say this collection: 3 2 2 1. When this algorithm will encounter 2 and compare it with 2, it may reverse them.
Sorting algorithms stability.
By the way, in case you don't care about the order of identical items in your collection, then you may chose the fastest one.
ACV
- 9,964
- 5
- 76
- 81
2
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, 5In I/P 3(b) comes after 3(a) and the same stays intact in the O/P.
It can be explained very easily. Let us take the following example:
3,3,2,1
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.
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 comes the 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:
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)
-
I do not think this is correct. If you did not sort in place you would not have this issue. I think the problem comes in when you put 3b on top of the heap and it does not swap down because it is equal to 3a. – TheCodeNovice May 03 '18 at 14:21
-
@TheCodeNovice Take a look at this https://stackoverflow.com/questions/19336881/why-isnt-heapsort-stable – Sumeet May 03 '18 at 14:41
-
1
