Why Selection sort can be stable or unstable

Question

I know that selection sort can be implemented as stable or unstable. But I wonder how it can be. I think sort algorithm can be only stable or only unstable. Can someone explain?

Answer 1

Basically in selection sort, swap that occurs at the end of each "round" can change the relative order of items having the same value.

for example, suppose you sorted 4 2 3 4 1 with selection sort.

the first "round" will go through each element looking for the minimum element. it will find that 1 is the minimum element. then it will swap the 1 into the first spot. this will cause the 4 in the first spot to go into the last spot: 1 2 3 4 4

now the relative order of the 4's has changed. the "first" 4 in the original list has been moved to a spot after the other 4.

remember the definition of stable is that

the relative order of elements with the same value is maintained.

Well, selection sort works by finding the 'least' value in a set of values, then swap it with the first value:

Code:

2, 3, 1, 1 # scan 0 to n and find 'least' value

1, 3, 2, 1 # swap 'least' with element 0.

1, 3, 2, 1 # scan 1 to n and find 'least' value

1, 1, 2, 3 # swap 'least' with element 1.

...and so on until it is sorted.

To make this stable, instead of swaping values, insert the 'least' value instead:

Code:

2, 3, 1, 1 # scan 0 to n and find 'least' value

1, 2, 3, 1 # insert 'least' at pos 0, pushing other elements back.

1, 3, 2, 1 # scan 1 to n and find 'least' value

1, 1, 2, 3 # insert 'least' at pos 1, pushing other elements back.

...and so on until it is sorted.

It shouldn't be too hard to modify an unstable selection sort algorithm to become stable.

Answer 2

In common case - you're not correct. Selection sorting is unstable. That comes from it's definition. So, you're obviously confused with one custom case.

It can be stable - normally, only with linked lists. To do that (classic way, O(1) memory) - instead of swaps, minimal element must be linked to the unsorted part, making entire algorithm stable. And this is the difference in "implementation" - which, obviously, will produce stability only in this case due to data structure specifics. It has nothing to do with common case, when selection sorting is unstable