Self doubt

Question

When sorting technique is called stable?

Comments

When relative ordering of equal keys is preserved after sorting then it is called stable.

Eg: Let the array of elements be :   5₁,2₁,5₂,4,2₂,1

The subscript is used to mark the relative positions of two equal elements.

After sorting if the array becomes:  1,2₁,2₂,5₁,5₂ then the sorting technique is stable. Bubble sort, Insertion sort, selection sort, merge sort are stable while quick sort and heap sort are not.

In case of unstable sorting algo the sorted array may become: 1,2₂,2₁,5₂,5₁

---

Selection sort is not a stable sorting algorithm

---

1.https://www.geeksforgeeks.org/stable-selection-sort/

Selection sort can be made Stable if instead of swapping, the minimum element is placed in its position without swapping i.e. by placing the number in its position by pushing every element one step forward.

2. https://stackoverflow.com/questions/20761396/why-selection-sort-can-be-stable-or-unstable

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

---

How selection sort is stable??

Answer 1

Stable sorting algorithms maintain the relative order of records with equal value. That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

Example: merge sort, insertion sort ,bubble sort

• In below example 4 have repeated . Now when we sort them then 4a must be come first. Becz in orignal list 4a comes first .

2 , 4a , 6, 4b ,8 

Sort above list 

2 ,4a, 4b ,6, 8 

Comments

bubble and insertion are stable