Stable Sort Method - Where Can I Get One?

  • Thread starter Thread starter Gary Brown
  • Start date Start date
G

Gary Brown

Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
 
Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...

I disagree with your assertion that you can't find one in the
framework. Can you state what your issues are? What are you trying to
sort etc? I mean if you are doing pre-order traversals and binary tree
sorts I could see your point. But for simple sorts using the IComparer
interface you should be well suited for 'stable' sorts, I cant speak
to efficiency but that is another post all together.

PD
 
Gary,

Why not use the static Sort method on the Array class, or the Sort
method on the List<T> class? You can easily store your items in these
structures and then use a custom comparer to compare instances of the items.
Then, the Sort method will do the rest for you.
 
Hey Nicholas,

AFAIK these sorts are *not* stable. Definitely the List<T> one isn't, I just
did a quick test.

Cheers
Doug Forster

Nicholas Paldino said:
Gary,

Why not use the static Sort method on the Array class, or the Sort
method on the List<T> class? You can easily store your items in these
structures and then use a custom comparer to compare instances of the
items. Then, the Sort method will do the rest for you.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Gary Brown said:
Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...
Click to expand...
 
Hey Nicholas,

AFAIK these sorts are *not* stable. Definitely the List<T> one isn't, I just
did a quick test.

Cheers
Doug Forster

message




- Show quoted text -
Click to expand...

Can you please define stable?
 
Doug,

Care to say what makes them not stable? I've definitely never had an
erroneous result using them.

--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Doug Forster said:
Hey Nicholas,

AFAIK these sorts are *not* stable. Definitely the List<T> one isn't, I
just did a quick test.

Cheers
Doug Forster

Nicholas Paldino said:
Gary,

Why not use the static Sort method on the Array class, or the Sort
method on the List<T> class? You can easily store your items in these
structures and then use a custom comparer to compare instances of the
items. Then, the Sort method will do the rest for you.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Gary Brown said:
Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...
Click to expand...
Click to expand...
 
A stable sort is one that preserves the existing order of equal keys.

Nicholas Paldino said:
Doug,

Care to say what makes them not stable? I've definitely never had an
erroneous result using them.

--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Doug Forster said:
Hey Nicholas,

AFAIK these sorts are *not* stable. Definitely the List<T> one isn't, I
just did a quick test.

Cheers
Doug Forster

Nicholas Paldino said:
Gary,

Why not use the static Sort method on the Array class, or the Sort
method on the List<T> class? You can easily store your items in these
structures and then use a custom comparer to compare instances of the
items. Then, the Sort method will do the rest for you.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...
Click to expand...
Click to expand...
 
Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...
Merge sort is stable, you could look for that.

Alternatively add an "int order;" field to your class and when you
want to sort a collection, just run down the collection assigning
order as 0, 1, 2, 3, 4 ... Then write your own comparer function to
sort on other criteria, resolving ties by using the order variable.
That will produce a stable sort if you pass it to the collection's own
sort routine.

rossum
 
Doug Forster said:
A stable sort is one that preserves the existing order of equal keys.
Click to expand...

In particular, here's an example of List<T>.Sort being unstable:

using System;
using System.Collections.Generic;

class Data : IComparable<Data>
{
string name;

public Data (string name)
{
this.name = name;
}

public int CompareTo(Data other)
{
return 0; // All items are equal to each other
}

public override string ToString()
{
return name;
}
}

class Test
{
static void Main()
{
List<Data> list = new List<Data>();

list.Add (new Data("First"));
list.Add (new Data("Second"));
list.Add (new Data("Third"));

list.Sort();
foreach (Data data in list)
{
Console.WriteLine(data);
}
}
}

If Sort were stable, this would be guaranteed to print
First
Second
Third

As it is, it always prints
Third
Second
First
(on my box at least)
 
Furthermore, the only stable sort I can find is the overload of the Sort
method on the Array class which takes an array of keys, and an array of
items, and maintains the order of the items for similar keys.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Doug Forster said:
A stable sort is one that preserves the existing order of equal keys.

Nicholas Paldino said:
Doug,

Care to say what makes them not stable? I've definitely never had an
erroneous result using them.

--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Doug Forster said:
Hey Nicholas,

AFAIK these sorts are *not* stable. Definitely the List<T> one isn't, I
just did a quick test.

Cheers
Doug Forster

in message Gary,

Why not use the static Sort method on the Array class, or the Sort
method on the List<T> class? You can easily store your items in these
structures and then use a custom comparer to compare instances of the
items. Then, the Sort method will do the rest for you.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...
Click to expand...
Click to expand...
 
This seems to work on my PC.

List<Data> list = new List<Data>();

list.Add(new Data("First"));
list.Add(new Data("Second"));
list.Add(new Data("Third"));
Array.Sort(list.ToArray());

foreach (Data data in list)
{
Console.WriteLine(data);
}
 
Doug said:
A stable sort is one that preserves the existing order of equal keys.
Click to expand...

Then just make sure that the keys are not equal. Include a unique value
in the key.
 
Brette.Net said:
This seems to work on my PC.

List<Data> list = new List<Data>();

list.Add(new Data("First"));
list.Add(new Data("Second"));
list.Add(new Data("Third"));
Array.Sort(list.ToArray());

foreach (Data data in list)
{
Console.WriteLine(data);
}
Click to expand...

That's not actually sorting the list though. It's creating a copy of
the list as an array, sorting that array, and then printing out the
(unchanged) list.
 
Gary Brown said:
I need a stable sort and can find none in the MS libraries.
Click to expand...

Apparently I'm not the only one surprised that the provided
sorts (most if not all the QuickSort algorithm) are not stable.
A stable sort keeps items with identical keys in their original
order. This is often critical. QuickSort leaves them in random
order. The documentation for Array.Sort(), List<>.Sort(), and
the ListView column sort specifically state that they are not
stable. This not the same as incorrectly sorting dissimilar
keys nor that they are inconsistent in how they leave items
with identical keys.

As an example you might have a ListView with peoples
names in one column and their town of residence in another.
If you click on the column header above names you will get
all names in alphabetical order. If you then click on the towns
header you want to see the data sorted by towns but still have
the peoples names alphabetically within that town. That is a
stable sort. Quicksort will correctly sort by town but leave
peoples names within each town in an arbitrary order.

Unsorted columns:

Moot Harvard
Smith Harvard
Jones Harvard
Kahn Bolton
Reis Bolton

Sort on names:

Jones Harvard
Kahn Bolton
Moot Harvard
Reis Bolton
Smith Harvard

Then on town, a stable sort gives

Kahn Bolton
Reis Bolton
Jones Harvard
Moot Harvard
Smith Harvard

whereas an unstable might yield

Reis Bolton
Kahn Bolton
Moot Harvard
Smith Harvard
Jones Harvard

Ok, I've probably beaten that one to death. And I
still don't have a stable sort method. :-)

Gary
 
Brette.Net said:
This seems to work on my PC.

List<Data> list = new List<Data>();

list.Add(new Data("First"));
list.Add(new Data("Second"));
list.Add(new Data("Third"));
Click to expand...

You discard the sorted array here, without reinitializing the original
list instance based on the sorted results:
Array.Sort(list.ToArray());
Click to expand...

So, it's not all that surprising that the list remains in the original
order here:
foreach (Data data in list)
{
Console.WriteLine(data);
}
Click to expand...

Remember, List<>.ToArray() creates a whole new array based on the
elements of the List<>. Changes in the new array are not reflected back
to the original list.

Pete
 
I noticed you've encountered the "how dare you say the sort isn't stable"
reply :-)

I posted (quite some time ago) a reply to someone else looking for a stable
sort "algorithm" that included a link to a message in an archive where I had
posted some .Net code (in this case VB.Net code) that implemented a custom
version of IComparer that supported stable sorting. I called the method
"SortStable" but as I checked that link now I noticed it is no longer
active.

The problem then is how best to explain my solution. The code I
incorporated it into was part of a class library called CSLA so while the
code could be adapted it was written as a method of a base class and at a
minimum you'd have a bit of conversion work to do.

I can post the code but I fear it wouldn't make intuitive sense. Let me see
(I'm reading the code now) and it looks like what I did was to send the
index along with the data that would ordinarily be compared. In the Compare
method I do the standard compare on the data item. If they are equal (the
compare will return 0) I compare the subkey (the index) which I know for a
fact will "break the tie" while maintaining the order. The "data" may be
duplicated but the index can never be duplicated.

So does that help or you do want to see some random hunks of semi-relevant
VB.Net code?

Tom
 
Gary said:
Apparently I'm not the only one surprised that the provided
sorts (most if not all the QuickSort algorithm) are not stable.
Click to expand...

I'm not really sursprised. I haven't given it much though before know,
but I wouldn't expect the sorting to be stable. Most efficient sorting
algorithms just doesn't work that way.

Perhaps also because I'm used to how sorting works when you request data
from a database, where the order is completely undefined unless you
specify sorting. If you sort on only one field, the order is undefined
for records with the same value in that field. If you want a specific
order, you have to provide sorting that puts the record in that order.
 
I was mildly surprised, too, that the BCL doesn't offer a stable sort.
But as you can see most people don't even know what a stable sort is,
so I guess MS figured it won't matter. The responses here are sadly
typical in my experience. So much for people claiming that you don't
need a CS degree since you can learn it all on the job...

OTOH, adapting a sort routine from some algorithms text book like
Sedgewick's "Algorithms in Java" isn't all that hard. Here's a
version of insertion sort for C# with generics (.NET 2.0 and up):

/// <summary>
/// Sorts the specified <see cref="IList{T}"/> using the insertion
/// sort algorithm and the specified <see cref="Comparison{T}"/>
/// method.</summary>
/// <typeparam name="T">
/// The type of all elements in the specified <paramref name="list"/>.
/// </typeparam>
/// <param name="list">
/// The <see cref="IList{T}"/> to sort.</param>
/// <param name="comparison">
/// The <see cref="Comparison{T}"/> method that defines the sorting
/// order.</param>
/// <exception cref="ArgumentNullException">
/// <paramref name="list"/> or <paramref name="comparison"/> is a null
/// reference.</exception>
/// <remarks>
/// <b>InsertionSort</b> sorts the specified <paramref name="list"/>
/// using the insertion sort algorithm. Unlike the Quicksort
/// algorithms provided by the standard library, this is a stable
/// algorithm. That is, the relative order of any two elements for
/// which the specified <paramref name="comparison"/> method returns
/// zero remains unchanged.</remarks>

public static void InsertionSort<T>(
IList<T> list, Comparison<T> comparison) {

if (list == null)
throw new ArgumentNullException("list");
if (comparison == null)
throw new ArgumentNullException("comparison");

for (int j = 1; j < list.Count; j++) {
T key = list[j];

int i = j - 1;
for (; i >= 0 && comparison(list, key) > 0; i--)
list[i + 1] = list;

list[i + 1] = key;
}
}
 
Hi,

I need a stable sort and can find none in the MS libraries.
Is there a simple one available on the internet? It needed
for sorting various lists of maybe 1K elements - mostly
ListView columns.

I took an algorithms course many years ago and learned
to really hate writing sort routines or I would just write one.

Googles lists many tutorials and conversations but no
methods.

Thanks,
Gary
Click to expand...

Have you looked into the Wintellect's Power Collections?
http://www.wintellect.com/PowerCollections.aspx
 
Back
Top