Menu
Just wondering if someone could explain why an "unstable sort" is considered bad? Basically I don't see any situations where it would really matter. Could anyone care to provide one?
641
A stable sorting algorithm maintains the relative order of the items with equal sort keys. An unstable sorting algorithm does not. In other words, when a collection is sorted with a stable sorting algorithm, items with the same sort keys preserve their order after the collection is sorted.
If a sorting algorithm is said to be "unstable", this means that for any items that rank the same, the order of the tied members is not guaranteed to stay the same with successive sorts of that collection. For a 'stable' sort, the tied entries will always end up in the same order when sorted.
Selection sort It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
A sorting algorithm is said to be stable if it maintains the relative order of numbers/records in the case of tie i.e. if you need to sort 1 1 2 3 then if you don't change the order of those first two ones then your algorithm is stable, but if you swap them then it becomes unstable, despite the overall result or ...
If you have a GUI that allows people to sort on individual columns by clicking on that column, and you use a stable sort, then people who know can get a multi-column sort on columns A,B,C by clicking on columns C,B,A in that order. Because the sort is stable, when you click on B any records with equal keys under B will still be sorted by C so after clicking on B the records are sorted by B, C. Similarly, after you click on A, the records are sorted by A, B, C.
(Unfortunately, last time I tried this on some Microsoft product or other, it looked like it didn't use a stable sort, so it's not surprising this trick is not better known).
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
