1
$\begingroup$

One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm. Why selection sort is unstable and can we make a sort algorithm stable by changing its swap condition?

$\endgroup$
1
$\begingroup$

Just run an example. I will use colors to distinguish multiple elements with the same value and a $\mid$ to separate the unsorted part from the sorted part.

With the input

$\mid\color{blue}{2},3,\color{red}{2},1$

the first step will swap $\color{blue}{2}$ with $1$.

$1,\mid3,\color{red}{2},\color{blue}{2}$

The order of the $2$s changed. It continues

$1,\color{red}{2},\mid3,\color{blue}{2}$

$1,\color{red}{2},\color{blue}{2},\mid3$

So, the $2$s ended in a different order as they started.

To avoid this you can insert the smallest element of the unsorted part at the beginning of the unsorted part, instead of swapping it.

So, the first step would be

$1,\mid\color{blue}{2},3,\color{red}{2}$

The next step leaves it as it is.

$1,\color{blue}{2},\mid3,\color{red}{2}$

It continues with

$1,\color{blue}{2},\color{red}{2},\mid3$

To prove that this happens in general, observe that if an element with multiplicity is about to be moved, it must be the first element (from left to right) of that value appearing in the unsorted part. So, when it gets moved to the beginning of the unsorted part it continues appearing before all the elements of the same value appearing in the unsorted part and after all the elements of the same value that could already be in the sorted part.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.