sorting - C# - Sort items of linked list by date

Question

I am having a Node

public class Node
{
    public Node(Pupil pupil)
    {
        Data = pupil;
        Next = null;
    }
    public Pupil Data { get; set; }
    public Node Next { get; set; }
}

which holds the date of birth of a student. I insert objects to the list like this

public void Insert(Pupil pupil)
{
    if (_head == null)
    {
        _head = new Node(pupil);
        return;
    }

    Node current = _head;

    while (current.Next != null)
    {
        current = current.Next;
    }

    current.Next = new Node(pupil);
}

But now i have the problem to sort the pupils by date of birth (pupil.DateOfBirth). Since I am new to Lists etc. I dont have an idea how to do this. Since corona is here we have to basically teach it ourselves in university. Help would be really appreciated.

Answer 1

Suppose you have an object called unorderedList (containing your pupils in an unordered fashion) and an object called orderedList, which initially is empty. Then you can do the following:

1. Take an element of unorderedList. It is not important which element you take. For example, you can always take the first one (which is also a good idea if the list is already partially ordered). Let's call this element temp.
2. Add temp to the correct position of orderedList.
3. Remove temp from unorderedList.
4. Do steps 1-3 until unorderedList is empty.

This algorithm is called insertion sort. The Wikipedia article on insertion sort also contains an implementation in C. You could take a look at it to get an idea how you could do it in C#.

Insertion sort is a rather primitive sorting approach. Other approaches (such as quicksort, mergesort, etc.) may be faster, but are also harder to implement.