Stability of sorting algorithms...

Jun 20, 2008 at 2:55 PM
Edited Jun 20, 2008 at 9:03 PM
Hi, good job!!!
I'm a Luca's friend and I'm currently programming in .NET (sometimes with Luca, at university).

.NET is a very powerful and interesting framework, but IHMO I think it
lacks control over sorting algorithms. What I'm trying to point out is
about stability of a sorting algorithm.
A sorting algorithm is stable if maintains the relative order of records
with equal keys (i.e., values). 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.
This property isn't critical when you are dealing with base types like
integers or strings, but can be very useful when you are sorting more
complex objects. I mean, suppose you have a simple array of integers,
like this:
[6 5 2 5 1 7 1]
sorting it is straigthforward, we always obtain:
[1 1 2 5 5 6 7]
The first two integers of the sorted array are 1 1. Reversing the order
of this two integers doesn't change the array. So, for example, when you
are sorting a random array that contains two 1's, the 1 1 sequence
appearing in the sorted array will always be the same, no matter if the
algorithm you are using is stable or not.
Now think you have an array of animals, and that you are sorting by
number of legs. Now stability makes the difference:
To figure out why, suppose you have this two arrays:

[cow, snake, dog, cat, chicken, ant]

and:

[dog, ant, chicken, cow, cat]

with an unstable algorithm you can obtain:

[snake, chicken, cow, dog, cat, ant]

and:

[chicken, dog, cow, cat, ant]

with a stable algorithm:

[snake, chicken, cow, dog, cat, ant]

and:

[chicken, cow, dog, cat, ant]

As you can see, the stable version of the algorithm always preserves the
order of the sequence [cow, dog, cat] (although this order is arbitrary)
in every array containings these animals, while the other MAY not.
.NET doesn't allow the programmer to know if the sorting algorithm
he/she's using is stable or not (some algorithms can be either stable or
unstable).
I'd like to deal with a stability-aware DSA framework!!! :)
Coordinator
Jun 21, 2008 at 5:29 PM
Hi Gianluca,

For now what I will say is that we will look into it BUT you can actually take a more atomic approach over sorting by implementing the IComparable interface on the complex types, this is what DSA sorting algorithms use to verify who is larger than who, less than etc.

Thanks for the comment and I will add it to our unofficial to-look-at list.

Thanks,

Granville
Jun 22, 2008 at 9:52 AM
Yes, IComparable interface allows deeper control over sorting. In fact I use to reimplement this interface to get the right behavior from my sorting algorithm (i.e. sorting again over equal key objects to break the tie). However, I think that the stability is a very basic property of a sorting algorithm and it should not be left to reimplement over and over again.

Gianluca
Coordinator
Jun 22, 2008 at 12:29 PM


GianlucaGhettini wrote:
Yes, IComparable interface allows deeper control over sorting. In fact I use to reimplement this interface to get the right behavior from my sorting algorithm (i.e. sorting again over equal key objects to break the tie). However, I think that the stability is a very basic property of a sorting algorithm and it should not be left to reimplement over and over again.

Gianluca



There is a fine line between giving the programmer more control, and providing generalised solutions - all I can say is that we will look at it.

Thanks for your feedback!

Granville