Algorithm for sorting a list of objects in c#

Question

Hi,

I have a list of object I wish to sort in C#.Net 3.5, the object is as follows

id | name | parent_id

1 | Superman | NULL

2 | Batman | 3

3 | Watchman | 1

4 | Wolverine | 2

I know some of you might find this easy, but I need to sort the list based on the parent_id, which is pointing to its own index(id) in the same table.

So can someone give me a good algorithm to sort this list without looping over and over again? I cannot really phrase it that well, therefore I can't seem to google the right results I wanted.

A collection of IEnumerable or DataTable solution would be great.

Thanks in advance.

EDIT:----------------NEW Example

id | name | parent_id

1 | TOP CHILD | NULL

2 | Child C | 3

3 | Child B | 4

4 | Child A | 1

----> The Output I want is

id | name | parent_id

1 | TOP CHILD | NULL

4 | Child A | 1

3 | Child B | 4

2 | Child C | 3

----> If I use OrderBy or Sort, the result I get is

id | name | parent_id

1 | TOP CHILD | NULL

4 | Child A | 1

2 | Child C | 3

3 | Child B | 4

--> Non of the solutions is what I really wanted, Sorry again for not being clear

Hope this example is clearer

Answer 1

I don't know any C# but I'm sure there is something called a "comparator function/object" in c#. C# should have some sort of library functions for sorting. Simply pass in your collection and your comparator function and it should be able to sort the collection for you.

Answer 2

Easy way:

using System.Linq;
...
var sorted = unsorted.OrderBy(x=>x.parent_id);

More complicated/reusable way:

In .NET you can use existing sorting facilities (like Array.Sort, List.Sort, LINQ's OrderBy, etc) just by replacing one single method. You need to implement a comparer (either by creating an object that implements IComparer, implementing IComparable on the objects being compared, or using a Comparison delegate.)

All the comparer's job is is to determine whether a given object is greater than or less than another object. As long as you do that and follow some basic rules (ie. if X is greater than Y, then Y must be less than X) then the sorting will be quick and painless.

Answer 3

If you implement IComparable in you object, you can use the .Sort method on an Array or ArrayList collection.

Answer 4

You can create a class for the above data with id, name, parent_id as class members. Override the CompareTo method of IComparable

    public class Person : IComparable<Person>
        {
            public int id, parentID;
            public string name;

            public Person(int id, string name, int parentID)
            {
                this.id = id;
                this.name = name;
                this.parentID = parentID;
            }

            #region IComparable Members

            public int CompareTo(Person obj)
        {
        return this.parentID.CompareTo(obj.parentID);

        //OR 
        //if (this.parentID > obj.parentID)
        //{
        //    return 1;
        //}
        //else if (this.parentID < obj.parentID)
        //{
        //    return -1;
        //}

        //return 0;
        }        
            #endregion
        }

In the main code:

List<Person> peopleArray = new List<Person>();
            peopleArray.Add(new Person(1, "Jerry", 1));
        peopleArray.Add(new Person(2, "George", 4));
        peopleArray.Add(new Person(3, "Elaine", 3));
        peopleArray.Add(new Person(4, "Kramer", 2));    
            peopleArray.Sort();

            foreach (Person p in peopleArray)
                Console.WriteLine(p.parentID);

This will sort the list by parent id O/P of parent ids: 1 2 3 4

Answer 5

I guess you want the NULL parentId to be the first, followed by its child.
If so, you can call OrderBy on the list using linq.

OrderBy(x => Convert.ToInt32(x.ParentId == null ? "0" : x.ParentId));

I am assuming ParentId is a string (it can not be null if it is an int).
And assuming that the list won't have Id = 0.

EDIT: This will print the items in the following order
Superman
Watchman
Wolverine
Batman

Answer 6

after you edit: I think I get you and the comparer looks like:

public Int32 CompareTo(SuperHero right)
{
    if (this.ID == right.ID)
        return 0;

    return this.ParentID.CompareTo(right.ID);
}

in response to your comment:

The class looks like:

public class SuperHero : IComparable<SuperHero>
{
    public Int32 ID { get; set; }
    public String Name { get; set; }
    public Int32 ParentID { get; set; }

    public SuperHero(Int32 id, String name, Int32 pid)
    {
        this.ID = id;
        this.Name = name;
        this.ParentID = pid;
    }

    public Int32 CompareTo(SuperHero right)
    {
        if (this.ID == right.ID)
            return 0;

        return this.ParentID.CompareTo(right.ID);
    }

    public override string ToString()
    {
        return this.Name;
    }
}

and to use it:

static void Main(string[] args)
{
    // create your list
    List<SuperHero> heroes = new List<SuperHero>();

    // populate it
    heroes.Add(new SuperHero(1, "Superman", 0));
    heroes.Add(new SuperHero(2, "Batman", 3));
    heroes.Add(new SuperHero(3, "Watchman", 1));
    heroes.Add(new SuperHero(4, "Wolverine", 2));

    foreach (SuperHero hero in heroes)
        Console.WriteLine(hero.ToString());
    Console.WriteLine();

    // sort it
    heroes.Sort();

    foreach (SuperHero hero in heroes)
        Console.WriteLine(hero.ToString());

    Console.ReadKey();
}

The .NET sort (QuickSort) will use your comparer to sort the list.