A Question of 'Sorts'?

  • Thread starter Thread starter TC
  • Start date Start date
T

TC

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
 
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;
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?
 
TC said:
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;
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?
Click to expand...


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...)
 
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?
Click to expand...

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;
TValue value = selector(item);
j = i - 1;
while ((j >= 0) && (comparer.Compare(selector(list[j]), value))
0)
Click to expand...
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = item;
}
}
}
 
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
 
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




Jon Skeet said:
TC said:
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;
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?
Click to expand...


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...)
Click to expand...
 
/// <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);
}
}
 
/// <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);
}
}


TC said:
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
Click to expand...
Click to expand...


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.
 
Back
Top