These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).
##Stability (Sorts)
####Definition
- ability of a sort to keep the current order of equal items while sorting.
- important if sorting by different keys (e.g. first by song name, then by artist)
####Stable sorts
| Sort | Stability |
|---|---|
| Insertion Sort | Stable |
| Mergesort | Stable (if merge is stable) |
| Selection Sort | Unstable |
| Shellsort | Unstable |
####Method of Determining Stability
-
check if sorts move equal items past each other
[B] [A] [A] - sort first A
[A] [B] [A]
[A] [B] [A] - sort second A
[A] [A] [B] - stable if it doesn't go further
[A] [A] [B] - unstable -
algorithms that move/exchange items over long distances tend to be unstable
-
the way that algorithms are coded is critical to determining stability
- two Mergesorts coded slightly differently might have different stabilities