How to make selection sort stable?

[MartinCz]

Hi,

Selection sort is normally unstable but it can be implemented as stable.

I need this for school. Our lecturer proclaimed that the one who will find the solution and add it to the English WikiPedia will gain 3 points.

I searched the web, but could not find anything. The selection sort really can be stable and keep its quadratic asymptotic complexity at the same time.

But how to do this?

Thank you all in advance for your answers.

Regards,
MartinCz.

[wildfrog]

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

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:

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.

- petter

[MartinCz]

Hi Peter,

Thank you a lot for your reply.

Does this still have a quadratic complexity?

I am not sure if this is what my lecturer wants to see. Your solutions is rather something between insert sort and select sort.

I am not sure , but I think we did the stable sort method at our lesson. We did some optimization for some alogorithm but I am just not sure whether it was select sort and wether it was connected with "making stable". :)

The trick was having two indexes. When looking for the minimum, we also saved the previous minimum index. And this was used to constrain the next minimum looking process.

The problem is that this is all I remember?

Have you encountered this trick?

Thank you in advance.

Regards,
MartinCz.

[wildfrog]

As far as I can see this still has quadratic complexity, but if you're working with arrays then O(n) swaps becomes O(n) inserts and O(n^2) moves. If you use linked lists you'll end up with O(n) inserts.

- petter