Why Selection sort can be stable or unstable

user_2960751 0
Viewed 39430

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?

sorting arrays algorithm
5 Answers
  • First, you have to understand that there is nothing unstable kind of thing with the Selection sort as it vividly depends upon the data structure you are using for the specific.
  • For example, consider the fact that we have an array as 4 2 4 1 and upon sorting this array using the traditional method the result will be 1 2 4 4, simple. But during the first round of the iteration, the 4 which is present at the 0th index will be placed at the last index which is ethically wrong considering the fact of stability as the 4 which is present on the 2nd index should come later than the 4 present on the 0th index. ( 1 2 4[2nd index] 4[from 0th index])
  • If asked! You can make a slight modification in the implementation and instead of swapping the numbers, choose the minimum element during the first round and then place that element at its correct position and shift the whole array. I know the shifting operation might cost more than the swapping but this is the best I can think of.
  • If you are concerned about the shifting operation, you may use the Linked list rather than the array and insert the appropriate element at its appropriate position in O(1) time.
user_159589690
Related