Search code examples
javaalgorithmsortingstability

Why selection sort is unstable?

Question: I was going through the list of sorts and found a very intriguing image of all sort stabilities.I am not going to ask what does the stability of sorting mean since it has already been answered.My question is how selection sort ,is unstable since it is so widely used.

Here is the image of the sorts and their stability and complexities:-

Image of all sorts

As you can see from the image the last column provides us the stability of each of these sorts.

Source of image:-

https://medium.com/@_marcos_otero/the-real-10-algorithms-that-dominate-our-world-e95fa9f16c04

I am not experienced with quick and heapsort but I am used to selection sort and used it in various programs and never found any kind of unstable behaviour.I know that the complexity wise bubblesort is far better than selection sort but there actual work is same which is sorting and arranging a group of values either in ascending or descending order right?So this stability in sortings is a bit confusing and mostly forces me to think how one sort is stabler than the other.

Can anyone explain me the unstable behaviour and how their stabilities differ with respect to their complexities in these sortings?

Solution

  • What makes selection sort unstable is that the step of swapping a pair of elements could possibly change the relative order of another pair of elements that have equal keys. For instance, when sorting the array

    2 2' 1

    since the element with the minimum key is 1, you'll have to push it to the lowest position of the array by swapping 1 with 2:

    1 2' 2

    Swapping 1 with 2 changed the relative order of the two equal elements (2' and 2).

    That is, two elements with equal keys do not appear in the same order in the sorted output as they appear in the input array. Hence, selection sort is unstable.