.NET Forum / Languages / C# / March 2008
A Question of 'Sorts'?
|
|
Thread rating:  |
TC - 26 Feb 2008 05:27 GMT Hey All,
I recently saw the following on CodeProject:
http://www.codeproject.com/script/Membership/Profiles.aspx?mid=36803
and I have a question regarding Generics and the sorting of objects.
Assuming I have the following classes: using System; using System.Collections.Generic; using System.Text; namespace JunkTest { // Enumeration of sorder order types public enum SortOrderType { Ascending, Descending } // Enumeration of comparison types public enum PersonComparisonType { LastName, FirstName, Age } public class Person : IComparable<Person> { private string _lastName = null; public string LastName { get { return _lastName; } set { _lastName = value; } } private string _firstName = null; public string FirstName { get { return _firstName; } set { _firstName = value; } } private int _age = 0; public int Age { get { return _age; } set { _age = value; } } public Person(string lastName, string firstName, int age) { this.LastName = lastName; this.FirstName = firstName; this.Age = age; } public Person() { } public int CompareTo(Person person) { return this.LastName.CompareTo(person.LastName); } // Special implementation to be called by custom comparer public int CompareTo(Person person, PersonComparisonType comparisonType) { switch (comparisonType) { case PersonComparisonType.LastName: return this.LastName.CompareTo(person.LastName); case PersonComparisonType.FirstName: return this.FirstName.CompareTo(person.FirstName); case PersonComparisonType.Age: return this.Age.CompareTo(person.Age); } return 0; } } public class PersonComparer : IComparer<Person> { private PersonComparisonType comparisonType = PersonComparisonType.LastName; public PersonComparisonType ComparisonType { get { return comparisonType; } set { comparisonType = value; } } private SortOrderType sortOrder = SortOrderType.Ascending; public SortOrderType SortOrder { get { return sortOrder; } set { sortOrder = value; } } public PersonComparer(PersonComparisonType comparisonType) { this.comparisonType = comparisonType; } public bool Equals(Person lhs, Person rhs) { return this.Compare(lhs, rhs) == 0; } // Tell the Person objects to compare themselves public int Compare(Person lhs, Person rhs) { switch (sortOrder) { case SortOrderType.Ascending: default: return lhs.CompareTo(rhs, comparisonType); case SortOrderType.Descending: return rhs.CompareTo(lhs, comparisonType); } } } }
I was wondering how one would implement their own QuickSort or BubbleSort algorithm like you did in the article?
Currently, for example, I do the following:
Person ThisPerson = new Person(); Person ThatPerson = new Person(); Person OtherPerson = new Person();
ThisPerson.Age = 25; ThisPerson.FirstName = "Tom"; ThisPerson.LastName = "Carr"; MyTotalPersons.Add (ThisPerson);
OtherPerson.Age = 31; OtherPerson.FirstName = "Kelly"; OtherPerson.LastName = "Britton"; MyTotalPersons.Add(OtherPerson);
ThatPerson.Age = 28; ThatPerson.FirstName = "James"; ThatPerson.LastName = "Karl"; MyTotalPersons.Add (ThatPerson);
// Sort collection using age PersonComparer personComparer = new PersonComparer(PersonComparisonType.LastName); personComparer.SortOrder = SortOrderType.Descending; MyTotalPersons.Sort(personComparer);
where 'MyTotalPersons' is declared as follows:
private List<Person> MyTotalPersons=new List<Person>();
The above calls the default built-in sort. How would one implement such algorithms for objects using Generics?
Thanks,
TC
TC - 26 Feb 2008 05:34 GMT Perhaps an even simpler question / example, consider the following:
static void InsertSort<T>(IList<T> list) where T : IComparable<T> { int i, j;
for (i = 1; i < list.Count; i++) { T value = list[i]; j = i - 1; while ((j >= 0) && (list[j].CompareTo(value) > 0)) { list[j + 1] = list[j]; j--; } list[j + 1] = value; } }
How can I change the above to sort on a property of the list item?
> Hey All, > [quoted text clipped - 150 lines] > > TC Jon Skeet [C# MVP] - 26 Feb 2008 08:16 GMT > Perhaps an even simpler question / example, consider the following: > [quoted text clipped - 16 lines] > > How can I change the above to sort on a property of the list item? Instead of relying on IComparable, make your method either take an IComparer<T> or a Comparison<T> and make that perform the comparisons.
(As recommended in your previous thread about sorting...)
 Signature Jon Skeet - <skeet@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet World class .NET training in the UK: http://iterativetraining.co.uk
TC - 26 Feb 2008 18:38 GMT Jon,
I am familiar with the other method. I've been asked to build a custom sort algorithm so I will have to implement something like that below.
-- Todd
>> Perhaps an even simpler question / example, consider the following: >> [quoted text clipped - 21 lines] > > (As recommended in your previous thread about sorting...) Marc Gravell - 26 Feb 2008 08:21 GMT > Perhaps an even simpler question / example, consider the following: // snip
> How can I change the above to sort on a property of the list item? In C# 3, I would very very tempted to use a lambda to do this type of selection:
using System; using System.Collections.Generic;
class DemoData { public int Value1 { get; set; } public double Value2 { get; set; } }
static class Program { static void Main(string[] args) { List<DemoData> data = new List<DemoData>(); Random rand = new Random(123456); for (int i = 0; i < 500; i++) { data.Add(new DemoData { Value1 = rand.Next(500), Value2 = rand.NextDouble() * 500 }); } data.InSituSort(row => row.Value2); foreach (var row in data) { Console.WriteLine("{0}\t{1}", row.Value1, row.Value2); } } static void InSituSort<TSource, TValue>( this IList<TSource> list, Func<TSource, TValue> selector) { Sort(list, selector, Comparer<TValue>.Default); } static void Sort<TSource, TValue>( this IList<TSource> list, Func<TSource, TValue> selector, IComparer<TValue> comparer) {
int i, j;
for (i = 1; i < list.Count; i++) { TSource item = list[i]; TValue value = selector(item); j = i - 1; while ((j >= 0) && (comparer.Compare(selector(list[j]), value))
> 0) { list[j + 1] = list[j]; j--; } list[j + 1] = item; } } }
Marc Gravell - 26 Feb 2008 08:32 GMT Actually Jon has a good point; it would be more flexible to do the main code based just on an IComparer<T> (where T is the item in your list) - however, I do have a supply of classes that implement IComparer<T> based on a Func<T, TValue> if you want... allows simple specification of the property, and chaining multiple propeties together into a single IComparer<T>...
Marc
TC - 26 Feb 2008 19:04 GMT Hey Mark,
I'll contact you regarding the classes.
Thanks,
Todd
> Actually Jon has a good point; it would be more flexible to do the main > code based just on an IComparer<T> (where T is the item in your list) - [quoted text clipped - 4 lines] > > Marc TC - 02 Mar 2008 10:17 GMT /// <summary> /// A generic bubblesort method implementation /// Bubblesort Explanation: http://en.wikipedia.org/wiki/Bubblesort /// </summary> /// <typeparam name="T">The object type populating the list</typeparam> /// <param name="sourceList">A list of objects</param> /// <param name="customComparer">A custom comparer object used to compare the list items</param> public static void BubbleSort<T>(IList<T> sourceList, IComparer<T> customComparer) { try { // Ensure that no null values have been provided if (sourceList == null) { throw new ArgumentNullException("sourceList", Properties.Resources.NullParam); } else if (customComparer == null) { throw new ArgumentNullException("customComparer", Properties.Resources.NullParam); }
for (int counter = sourceList.Count - 1; counter >= 0; counter--) { // The inner loop ensures that all values are re-compared and swapped, if necessary for (int index = 1; index <= counter; index++) { if (customComparer.Compare(sourceList[index - 1], sourceList[index]) > 0) { // Create a temporary holding object and swap the order of the items T tempListItem = sourceList[index - 1]; sourceList[index - 1] = sourceList[index]; sourceList[index] = tempListItem; } } } } catch (System.Exception exception) { ExceptionHandler.HandleException(exception); } }
/// <summary> /// A generic quicksort method implementation /// </summary> /// <typeparam name="T">The object type populating the list</typeparam> /// <param name="sourceList">A list of objects</param> /// <param name="customComparer">A custom comparer object used to compare the list items</param> public static void QuickSort<T>(IList<T> sourceList, IComparer<T> customComparer) { try { // Ensure that no null values have been provided if (sourceList == null) { throw new ArgumentNullException("sourceList", Properties.Resources.NullParam); } else if (customComparer == null) { throw new ArgumentNullException("customComparer", Properties.Resources.NullParam); }
// Call the actual quicksort algorithm CustomObjectListSort.PrivateQuickSort(sourceList, customComparer, 0, sourceList.Count - 1); } catch (System.Exception exception) { ExceptionHandler.HandleException(exception); } } #endregion
#region Private Methods /// <summary> /// A generic quicksort algorithm implementation /// Quicksort Explanation: http://en.wikipedia.org/wiki/Quicksort /// </summary> /// <typeparam name="T">The object type populating the list</typeparam> /// <param name="sourceList">A list of objects</param> /// <param name="customComparer">A custom comparer object used to compare the list items</param> /// <param name="lowIndex">Lower index in the list</param> /// <param name="highIndex">Upper index in the list</param> private static void PrivateQuickSort<T>(IList<T> sourceList, IComparer<T> customComparer,int lowIndex, int highIndex) { try { // Ensure that no null values have been provided if (sourceList == null) { throw new ArgumentNullException("sourceList", Properties.Resources.NullParam); } else if (customComparer == null) { throw new ArgumentNullException("customComparer", Properties.Resources.NullParam); }
int tempLowIndex = lowIndex + 1; int tempHighIndex = highIndex;
// If the lowIndex is not less than the highIndex, the sort is complete if (lowIndex < highIndex) { // Create a temporary holding object for swapping the order of the items T tempListItem = sourceList[lowIndex];
// Loop through list until all items // between indices have been compared while (tempLowIndex < tempHighIndex) { // Keep incrementing temp indices until appropriate discrepancy for swap is found if (customComparer.Compare(sourceList[tempLowIndex], tempListItem) <= 0) { tempLowIndex++; } else if (customComparer.Compare(sourceList[tempHighIndex], tempListItem) >= 0) { tempHighIndex--; } else { tempListItem = sourceList[tempLowIndex]; sourceList[tempLowIndex] = sourceList[tempHighIndex]; sourceList[tempHighIndex] = tempListItem; } }
if (customComparer.Compare(sourceList[tempLowIndex], tempListItem) < 0) { // If tempLow is less than lowIndex, swap the items tempListItem = sourceList[tempLowIndex]; sourceList[tempLowIndex] = sourceList[lowIndex]; sourceList[lowIndex] = tempListItem; tempLowIndex--; } else { // Otherwise, swap item just below tempLow with the lowIndex tempLowIndex--; tempListItem = sourceList[tempLowIndex]; sourceList[tempLowIndex] = sourceList[lowIndex]; sourceList[lowIndex] = tempListItem; }
// Recursively call the quicksort function until both partitions // (i.e. 'lowIndex' and 'highIndex' pieces of list) are complete PrivateQuickSort(sourceList, customComparer, lowIndex, tempLowIndex); PrivateQuickSort(sourceList, customComparer, tempHighIndex, highIndex); } } catch (System.Exception exception) { ExceptionHandler.HandleException(exception); } }
> Hey All, > [quoted text clipped - 150 lines] > > TC Christopher Van Kirk - 03 Mar 2008 00:27 GMT > /// <summary> > /// A generic bubblesort method implementation [quoted text clipped - 337 lines] >> >> TC Just as an FYI...I've found that implementing your own sort in C# outperforms the one you get for free in List<> by about 10%. Furthermore, bin-searching a sorted list outperforms the Dictionary<> collection by about 20%. If you can pre-sort your collections, don't use the Dictionary object.
 Signature Posted via a free Usenet account from http://www.teranews.com
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|