Lean on a stable shield, and don’t fear the weapons.
What’s The Problem?
If we have a table of students, sorted according to students names. Now, if we sorted the table rows according to the student sections, students are no longer sorted by name!.
Stability is to maintain the same order when the data is being sorted with respect to another property.
So, once it’s sorted by name, then when sorting by section, it should maintain the sort by name within each section. So, we should get table ordered by section, and for every section, the names are sorted.
A sorting algorithm is said to be stable if it preserves the same order when the data is being sorted by another property.
How To Maintain Stability?
Some of the sorting algorithms are stable like Insertion sort and Mergesort, while other aren’t; Selection sort, Shellsort, Quicksort, and Heapsort.
Insertion sort and Mergesort
In these algorithms, just make sure if you have two elements x & y, where x is already placed before y in the array, then x must kept before y as long as y is greater than or equal to x. This way, x won’t precede y unless y is less than x.
Therefore, both of these algorithm don’t move equal items past each other. It preserves their current order.
Other (Selection sort, Shellsort, Quicksort, and Heapsort)
These algorithms don’t perverse the current order of data. Selection sort for example may swap two elements, while these two elements shouldn’t past each other to preserve the current order.
sorted by time then sorted by location(not stable)
LOCATION TIME LOCATION TIME
Chicago 9:00 Chicago 9:00
Houstin 9:03 Chicago 10:05
Phonix 9:13 Houstin 9:59
Houstin 9:59 Houstin 9:03
Chicago 10:05 Phonix 9:13
In the second iteration, Selection sort will swap “Chicago 10:05” with “Houstin 9:03”, and “Houstin 9:03” will precede “Houstin 9:59”, although it has smaller time value.