You can create a custom IComparer that accepts an array of keys you want to sort by that mimics a stable sorts and will provide the same results. For example, I will create a customer IComperer to sort out Employee Objects below:
Class Employee
Public FirstName AS String
Public Lastname AS String
Public JobTitle AS String
Public Sub New(FirstName AS String, LastName AS String, JobTItle AS String)
me.FirstName = FirstName
Me.LastName = LastName
Me.JObTItle = JobTitle
End SUb
End Class
Public Class EmployeeComparer
Generic.IComparer(Of Employee)
Private _FieldsToCompare As String()
Private _SortDirection As System.ComponentModel.ListSortDirection = ComponentModel.ListSortDirection.Ascending
Public Sub New(ByVal Field As String)
_FieldsToCompare = New String() {Field}
End Sub
Public Sub New(ByVal ParamArray Fields As String())
_FieldsToCompare = Fields
End Sub
Public Sub New(ByVal Field As String, ByVal Direction As System.ComponentModel.ListSortDirection)
_FieldsToCompare = New String() {Field}
_SortDirection = Direction
End Sub
Public Property FieldsToCompare() As String()
Get
Return _FieldsToCompare
End Get
Set(ByVal Value As String())
_FieldsToCompare = Value
End Set
End Property
Public Property SortDirection() As System.ComponentModel.ListSortDirection
Get
Return _SortDirection
End Get
Set(ByVal Value As System.ComponentModel.ListSortDirection)
_SortDirection = Value
End Set
End Property
Public Function Compare(ByVal A AsEmployee, ByVal B As Employee) As Integer Implements System.Collections.Generic.IComparer(Of Employee).Compare
Dim Value As Integer
For Each Field As StringIn _FieldsToCompare
Select Case Field
Case "FirstName" Value = CardA.FirstName.CompareTo(CardB.FirstName)
Case "LastName" Value = CardA.LastName.CompareTo(CardB.LastName)
Case "JobTitle" Value = CardA.JobTitle.CompareTo(CardB.JobTitle)
If Value <> 0 Then Return Value
Next
Return value
End Function
End Class
Basically, what the Icomparer above does it compare multiple keys. So if you want to sort by first name, then last name, then job position, you could do this:
Sub SOmeMethod()
Dim A AS List(OF Employee)
A.Add(new Employee("Joe", "Schmoe", "President"))
A.Add(new Employee("Bill", "Riley", "Manager"))
A.Add(new Employee("Bill", "Small", "Manager"))
A.Add(new Employee("Chris", "Jackman", "Advisor"))
A.Sort(new EmployeeComparer("FirstName", "Lastname"m "JobTitle"))
End Sub
This will sort the elements by FirstName, LastName, then Job Title.
It works by first sorting objects by the first name. In cases where the first names are the same, it then compares the last name. If they are different, then it returns the appropriate -1 or 1 based on the comparison. And FInally, it compares the job titles.
This will produce the same results as a stable sort using the default quicksort provided in .NET.
I hope this helps.
Gary Brown wrote:
Stable Sort Method - Where Can I Get One?
07-Aug-07
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
Previous Posts In This Thread:
Stable Sort Method - Where Can I Get One?
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
Re: Stable Sort Method - Where Can I Get One?
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
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)
RE: Stable Sort Method - Where Can I Get One?
look for Array.Sort in the documentation
:
Hey Nicholas,AFAIK these sorts are *not* stable.
Hey Nicholas,
AFAIK these sorts are *not* stable. Definitely the List<T> one is not, I just
did a quick test.
Cheers
Doug Forster
Re: Stable Sort Method - Where Can I Get One?
Can you please define stable?
Doug, Care to say what makes them not stable?
Doug,
Care to say what makes them not stable? I have definitely never had an
erroneous result using them.
--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)
A stable sort is one that preserves the existing order of equal keys.
A stable sort is one that preserves the existing order of equal keys.
Re: Stable Sort Method - Where Can I Get One?
On Tue, 7 Aug 2007 15:59:59 -0400, "Gary Brown"
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 is right.
Doug is right. I wasn't interpreting "stable" in the manner in which he
was (I was assuming stable meant, well, it works). Doug is referring to the
the classification of sorting.
The attached program shows that the Sort method on List<T> is not
stable. The output should show an Id of 3, not 2 for the second item with
Key = 20.
--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)
Re: Stable Sort Method - Where Can I Get One?
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)
--
Jon Skeet - <
[email protected]>
http://www.pobox.com/~skeet Blog:
http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Furthermore, the only stable sort I can find is the overload of the Sort
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)
This seems to work on my PC.List<Data> list = new List<Data>();list.
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);
}
Re: Stable Sort Method - Where Can I Get One?
Doug Forster wrote:
Then just make sure that the keys are not equal. Include a unique value
in the key.
--
G?ran Andersson
_____
http://www.guffa.com
Re: Stable Sort Method - Where Can I Get One?
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.
--
Jon Skeet - <
[email protected]>
http://www.pobox.com/~skeet Blog:
http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Re: Stable Sort Method - Where Can I Get One?
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.
Brette.Net wrote:
You discard the sorted array here, without reinitializing the original
list instance based on the sorted results:
So, it's not all that surprising that the list remains in the original
order here:
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"
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
Re: Stable Sort Method - Where Can I Get One?
Gary Brown wrote:
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.
--
G?ran Andersson
_____
http://www.guffa.com
I was mildly surprised, too, that the BCL doesn't offer a stable sort.
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;
}
}
--
http://www.kynosarges.de
Re: Stable Sort Method - Where Can I Get One?
Have you looked into the Wintellect's Power Collections?
http://www.wintellect.com/PowerCollections.aspx
in message
Well, I finally bit the bullet and wrote a merge sort. None of
the sorts that I found on the internet, Wintellect for example,
stated whether they were stable or not. It proved easier to
write one than wade through a lot of code to find a stable sort.
I finally got some use out my ancient (1974) editions of
Knuth's books on algorithms.
Thanks to all who responded,
Gary
Re: Stable Sort Method - Where Can I Get One?
See also this:
<http://www.covingtoninnovations.com/michael/blog/0607/index.html#060713A>
I was just looking for the same thing and found your discussions withuseful
I was just looking for the same thing and found your discussions with
useful and, err, not-as-useful replies. The Wintellect's
PowerCollections DO include a stable sort (as it also includes many
different Set implementations which Microsoft decided to leave away
due to laziness...) Just go to their main web page and open the
Specification to which there is a link. In there you can see that
there are three methods in the Wintellect.PowerCollections.Algorithms
class (not all are in the Specification as it is quite old...):
void StableSort<T>(IEnumerable<T>)
void StableSort<T>(IEnumerable<T>, Comparison<T>)
void StableSort<T>(IEnumerable<T>, IComparer<T>)
If you download the library you get also the full documentation which
has a lot more information, containers and algorithms than that
specification. It looks like they've been taking quite a lot of
influence from STL, but they have several implementations for the
containers (e.g. RB-tree and Hash).
Submitted via EggHeadCafe - Software Developer Portal of Choice
Build an ASP.NET HttpLog Filter Module
http://www.eggheadcafe.com/tutorial...f59-a6eaed3edc4b/build-an-aspnet-httplog.aspx