CODEWITHSUNDEEP
algorithmsorting
ripper234
ripper234

Reputation: 229988

Why is Selection Sort not stable?

This might be trivial, but I don't understand why the default implementation of Selection Sort is not stable?

At each iteration you find the minimum element in the remaining array. When finding this minimum, you can choose the first minimum you find, and only update it when an element is actually smaller than it. So, the chosen element at each iteration is the first minimum - meaning, it's first on the previous sort order. So, to my understanding, the current sort will not destroy an order generated by a previous sort on equal elements.

What am I missing?

Upvotes: 45

Views: 22753

Answers (4)

Saqlain Rai
Saqlain Rai

Reputation: 1

Selection sort is generally an unstable sorting algorithm. To understand this, let's consider an example: array = [3a, 7, 5, 3b, 2, 9] where 3a = 3b

After 1st iteration array = [2, 7, 5, 3b, 3a, 9]

Now, you can see that the order of 3a and 3b are interchanged. And you will end up with the result as array = [2, 3b, 3a, 5, 7, 9]

Which clearly shows that the algorithm has changed the relative order of elements and thus, is an unstable algorithm.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372664

The problem is that selection sort swaps elements from the front of the array into the spot vacated by the minimum element, which can mess up the sorted order. For example, suppose I'm sorting

(4, 0), (4, 1), (1, 0)

Selection sort first swaps the (1, 0) to the front:

(1, 0), (4, 1), (4, 0)

And now the (4, 0) and (4, 1) are out of order from where they started in the sort. Running this to completion leaves the elements in this order, and the 4s are out of order.

Hope this helps!

Upvotes: 23

Sachin Gupta
Sachin Gupta

Reputation: 1

Stable means does not calculate further if elements is already sorted, but it calculate till end hence it is not stable.

Upvotes: -19

fakemustache
fakemustache

Reputation: 846

A small example:

Let b = B in

< B > , < b > , < a > , < C > (with a < b < c)

After one cycle the sequence is sorted but the order of B and b has changed:

< a > , < b > , < B > , < c >

But you can however implement Selections Sort stable if you, instead of switching, insert the minimum value. But for that to be efficient you should have a data structure that supports insertion at a low cost or otherwise you end up with quadratic complexity.

Upvotes: 71

Related Questions