Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsFree MagazinesWhite PapersSubmit Content
Discussion GroupsASP.NETWindows FormsLanguages.NET FrameworkVisual Studio.NET
Articles.NET FrameworkASP.NETToolsWindows Forms
.NET DirectoryOpen Source ProjectsUser GroupsWeb Resources
Related Topics
Visual Basic 6SQL ServerMS AccessOther DB ProductsMS Server ProductsMore Topics ...

.NET Forum / Languages / C# / March 2008

Tip: Looking for answers? Try searching our database.

A Question of 'Sorts'?

Thread view: 
Enable EMail Alerts  Start New Thread
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


Rate this thread:







Free Magazines

Get 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 ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.