In reading about various sorting algorithms I've seen it mentioned that some are "stable" and some are not. What does that mean, and what tradeoffs are involved on that basis when selecting an algorithm?
9
-
33This question would be easily answered within a minute with wikipedia. en.wikipedia.org/wiki/Sorting_algorithm– Mare InfinitusCommented Jul 9, 2014 at 21:42
-
7@MareInfinitus More precisely : en.wikipedia.org/wiki/Sorting_algorithm#Stability– BЈовићCommented Jul 10, 2014 at 9:40
-
4This is a question lacking own research. Answered with a wikipedia picture. And it gets really good feedback, which somehow makes me sad. IMHO it should be closed, and not get upvotes.– Mare InfinitusCommented Jul 10, 2014 at 14:51
-
4On the other hand, I just saw this and learned something new. If I had known that I didn't know this then I could have researched it but because the OP asked the question I now know what I didn't know that I didn't know.– KazarkCommented Jul 10, 2014 at 17:28
-
4Generally, "just google it" or "look it up on wikipedia" are not considerable acceptable responses on StackExchange sites. Because they do not provide an answer to what the complainer is verifying as a valid question with the call to the authorities of google and wikipedia. IF the question is easily a duplicate of another question or questions within programmers.stackexchange, then you can complain.– Michael PaulukonisCommented Jul 14, 2014 at 20:00
|
Show 4 more comments
5 Answers
A stable sort is one which preserves the original order of the input set, where the comparison algorithm does not distinguish between two or more items.
Consider a sorting algorithm that sorts cards by rank, but not by suit. The stable sort will guarantee that the original order of cards having the same rank is preserved; the unstable sort will not.
answered Jul 9, 2014 at 20:53
-
43Correction: The unstable algorithm exhibits undefined behaviour when two elements are equal, it is perfectly possible that the order is sometimes preserved. Commented Jul 9, 2014 at 21:16
-
9Nice picture, very similar to wikipedia en.wikipedia.org/wiki/Sorting_algorithm Commented Jul 9, 2014 at 21:43
-
9@MareInfinitus: It's in the public domain. Check the attribution on the original image. Commented Jul 9, 2014 at 21:43
-
2A good picture explains faster and deeper than a lot of words on the average case. Legal issues were not what I wanted to talk about. Commented Jul 9, 2014 at 21:45
-
3@RobertHarvey Actually, I believe the editor is correct. Your post currently says that a stable sort preserves the ordering of cards in the same suit, but cards in the same suit will have different ranks and thus must be rearranged to achieve sorted order. For example the sort does not preserve the order of the 2 and the 5 of hearts. It's the ordering of cards with the same rank (and different suits) that makes the difference between stable and unstable.– David ZCommented Jul 11, 2014 at 5:03
Stable algorithms preserve the relative order of elements.
So a stable sorting algorithm will retain the relative order of values which compare as equal.
Consider a sorting algorithm where we sort a collection of 2d points based on their X dimension.
Collection to be sorted: {(6, 3), (5, 5), (6, 1), (1, 3)}
Stable Sorted: {(1, 3), (5, 5), (6, 3), (6, 1)}
Regular Sorted: Either {(1, 3), (5, 5), (6, 3), (6, 1)}, or {(1, 3), (5, 5), (6, 1), (6, 3)}
As for the tradeoff... well, stable sorting is less efficient, but sometimes you need it.
For example when a user clicks the a column header to sort values in a UI, it's reasonable to expect his previous sorting order to be used in the case of equal values.
-
2Is it less efficient though? It seems "obvious", but some of the best sorting algorithms are stable by nature (e.g. anything based on merge sort, such as Tim sort), they don't need to do any explicit extra work to be stable.– user7043Commented Jul 9, 2014 at 21:25
-
10Stable has nothing to do with performance in general. Mergesort runs in O(n*log n) and is stable. Heapsort has similar performance, but is not stable. Commented Jul 9, 2014 at 21:37
-
2"Stable" can also apply to data-structures, eg. a "stable heap" is a heap which dequeues items that have the same priority in the same order they were queued. This is very important for efficient path-finding algorithms. Commented Jul 9, 2014 at 23:08
-
1There are no stable sorts which are O(n ln n) comparisons and also O(1) on memory. Speed is not the only measure of efficiency. The fact that you can't stable sort in-place matters. Commented Jul 10, 2014 at 13:40
-
4@QuestionC It appears block sort is stable and fits those bounds.– user7043Commented Jul 10, 2014 at 15:28
A stable sort is one which preserves the original order of the input set, where the comparison algorithm does not distinguish between two or more items.
I think the best way to describe a stable sort is to describe the goal of a stable sort: sorting by multiple attributes (aka as multi-level)
If you wish to have a list of people ordered primarily by last name, then by first name, then by middle initial (if any) then by date of birth (in month name, day, year order if known)
There are four ways to achieve that, one, is to create an amalgamation that contains all sortable values and then sort on that:
“Doe John U June001975”
This has some problems with normalization (middle name June vs no middle name and birth month is June) and with direction (suppose you want the middle name sorted in reverse order).
The second way is to have the comparison check, check all attributes, but that requires adding something between the sorting algorithm and the attributes, and isn’t easily amiable to changing the direction of individual attributes.
The third solution is to sort by your primary attribute (in this case last name), then break it up into buckets by that attribute, then sort each bucket by the next attribute, and so forth until you get to your last attribute (here birth-year if any).
The fourth solution is a stable sort and multiple passes in reverse order of your final goal. You sort by birthdate, then by middle name, then by first name, then by last name. With a stable sort, sorting doesn’t disturb the existing order, so Jane Doe will always appear before John, and John NMI Doe will appear before John D Doe (NMI means blank or null).
The first 3 solutions require that all of the sort attributes be known in advance. The fourth naturally picks up the attributes as sorting is applied.
If the sort is to be applied by the user, then (a) sort time is not excessive and (b) they will expect an apparently stable sort. Which means that you would have to add complexity to any unstable sort in order to achieve an apparently stable sort.
Finally, unstable sorting is not inherently faster than stable sorting, frequently stability is the result of factors inherent in the algorithm and so comes for free so to speak (stability can be layered upon unstable algorithms, but then does come at some additional cost).
Bogo is an unstable sort, but it’s much worse than bubble sort. Bubble sort is probably the slowest sort you’ll see in actual use, but it gets “picked” not for its stability but because someone is reinventing the wheel (creating their own for some reason) and it or shaker sort is what they come up with. Quick sort and merge sort are generally considered roughly equal, quick sort is inherently unstable and merge sort is inherently stable.
-
Using a stable sort for multi-criteria sort is a bad idea due to inefficiency. Unless there are just two criteria, with the second being "original order". Commented May 11 at 16:37
-
@Deduplicator: which is what most users expect when clicking on a column in a grid to sort it and then clicking on another column to sort it. It is indeed less efficient than sorting both at once, but it’s a simpler interface for sorting– jmorenoCommented May 12 at 14:06
A small detail: A stable sort has the property that sorting a sorted array keeps the order of elements unchanged. With an unstable sort, if a sorted array contains equal elements, they may change their order.
