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?
Take the 2-minute tour
×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
|
|
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 suit is preserved; the unstable sort will not.
|
|||||||||||||||||||||
|
|
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: Stable Sorted: Regular Sorted: Either 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. |
|||||||||||||||||
|
