Stable and unstable sorting

Stable and unstable sorting

We have heard of this Stable term in several contexts. Well, to add to the list there is a comparison of sorting algorithms on the basis of Stable and unstable terms.

Let us understand the meaning of the Stable sorting algorithm.

Well, in general terms of Physics, what we now as a stable state?

A stable state is one in which when we displace the Centre of Gravity from one point to another, it settles itself and goes back to its original position.

Even in general terms, the stable term means fixed in a certain posture.

Thus, in the same way, if the input values do not change their order of input values in the sorted order then it is called a Stable sorting algorithm.

Seems confusing,

Ok, let's take an example and then try to understand this fact.

For example, if our inputted array is

Array: 3,2,4,5,7,6,4

NOTE: One 4 is in a different color, to denote that the red 4 was entered first and then the black 4 was entered.

Ok now that we are clear upon the aforementioned facts. Let us see how the sorted array will look. Let the sorting be done in the ascending order.

Thus, on sorting the array there can be two outputs.

Don't believe me?

Ok, I'll show you how.

1st output: 2,3,4,4,5,6,7

2nd output: 2,3,4,4,5,6,7

You might find there is nothing as such differences between the two outputs. Well, there is no difference in the sorting but there is one small difference.

Note the position of the red 4 and the black 4. In the 1st output red, 4 is before the black 4. Whereas in the second output the red 4 is after black 4.

According to the input, the red 4 was entered first and then the black 4 was entered. That pattern is followed in the 1st output but not in the second output. Hence, the former is a Stable sorting algorithm whereas the latter is an unstable sorting algorithm.

Examples of stable sorting algorithm: Bubble sort, Insertion sort, Merge sort, Counting sort, Tim sort

Examples of unstable sorting algorithm: Selection sort, Heap sort, Shell sort, Quicksort.

Although one may argue that how Selection sort an unstable sorting algorithm. But it is true. This is because it swaps the same elements too.

Though it is true that this property can be controlled by appropriate use of conditional statements and relational operators. Yet, it is possible to provide an unstable sorting condition. Hence, it falls under unstable sorting algorithms

On the other Bubble sort and merge sort provides appropriate positioning and by no means gives unstable condition. Hence, it is not an unstable sorting algorithm.