A guide to sorting

Stable and Unstable sorts

There are two kinds of sort algorithms: "stable sorts" and "unstable sorts". These terms refer to the action that is taken when two values compare as equal. If you have an array T0..size with two elements Tn and Tk for n < k, and these two elements compare equal, in a stable sort they will appear in the sorted output with the value that was in Tn preceding Tk. The output order preserves the original input order. An unstable sort, by contrast, there is no guarantee of the order of these two elements in the output.

"What difference does it make?" you may ask. After all, if I have an input sequence 1 7 3 4 3 5 2, and the output sequence is 1 2 3 3 4 5 7, what does it matter that the values 3 may be in a different order? Well, consider that what we have is not a set of simple scalar values, but a set of tuples: <year, name>. Suppose my input sequence is <1981, "Fred">, <1987, "Joe">, <1983, "Harry">, <1984, "Charles">, <1983, "Ellen">, <1985, "Mary"> and <1982, "Harriet">. Suppose that I only compare the year. Then in a stable sort, I am guaranteed that the output will be <1981, "Fred">, <1982, "Harriet">, <1983, "Harry">, <1983, "Ellen">, <1984, "Charles">, <1985, "Mary">, <1987, "Joe">. You have the guarantee that the order of the two 1983 entries in the output preserves the original order. In an unstable sort, you have no such guarantee, and those two elements might well have come out as <1983, "Ellen">, <1983, "Harry">.

Note that qsort is not specified as a stable sort. Whether it is or not is up to a particular implementation.

You might also like...

Comments

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“Measuring programming progress by lines of code is like measuring aircraft building progress by weight.” - Bill Gates