Sort on a custom Linked List using c#-CodePudding

I have created a custom Linked List , code given below . Now trying to implement a sort (its what I told to do, not the best choice I know) , how we can do in best possible time complexity or the best approach

my custom linked list my doubt is over the last node , in each phase of bubble sort should try to sort last and then start over from first node , how to handle the last node as its points to the first node

    public class CustomCircularList<T> : ICollection<T>, IEnumerable<T>
    {

        Node<T> head = null;
        Node<T> tail = null;
        int count = 0;
        readonly IEqualityComparer<T> comparer;

        public int Count { get { return count; } }
        public bool IsReadOnly { get { return false; } }

        public void Add(T item)
        {
            this.AddLast(item);
        }
         AddLast...
    }
}

my Node class has three properties

public T Value { get; private set; }
public Node<T> Next { get; set; }
public Node<T> Previous { get; set; }

I added IComparer to my class T like this and trying to work like below

 public class Fund: IComparer<Fund>
    {
        public string fundname{ get; set; }
        public int Compare([AllowNull] Fund x, [AllowNull] Fund y)
        {
            if (x == null || y == null)
            {
                return 0;
            }

            return x.fundname.CompareTo(y.fundname);
      }

CodePudding user response：

First of all, let me assume that Node<T> object has (at least) 2 standard properties: Value and Next:

public class Node<T> {
  ...
  public T Value {get; set;}
  public Node<T> Next {get;} 
}

Since you have circular linked list,

tail.Next == head

we can enumerate all items except the last one as

for (Node<T> node = head; !ReferenceEquals(node.Next, head); node = node.Next) {
  ...
}

Just for reference, should we have a linked list (non circular), the loop would be (all we should do is to change head to null):

for (Node<T> node = head; !ReferenceEquals(node.Next, null); node = node.Next) {
  ...
}

The code can be

public void BubbleSort(IComparer<T> comparer = null) {
  comparer ??= Comparer<T>.Default;

  if (comparer is null)
    throw new ArgumentNullException(nameof(comparer));

  if (head is null)
    return; // empty linked list

  bool agenda = true;

  while (agenda) {
    agenda = false;

    for (Node<T> node = head; !ReferenceEquals(node.Next, head); node = node.Next) 
      if (comparer.Compare(node.Value, node.Next.Value) > 0) {
        agenda = true;

        var help = node.Value; 
        node.Value = node.Next.Value;
        node.Next.Value = help;   
      } 
  } 
}

Edit: If you want to sort some custom type (T) you should either ensure the T implements IComparable<T>:

public class MyClass: IComparable<MyClass> {
  ...
  public int CompareTo(MyClass other) {
    TODO: return 0 if other == this, -1 if this < other,  1 if this > other
  }
}

or you should implement a comparer IComparer<MyClass> which you should provide as an argument:

public class MyComparer<MyClass> {
  public int Compare(MyClass x, MyClass y) {
    //TODO: return 0 when x == y, -1 when x < y, when x > y
  }
}

then

MyCircularLinkedList.BubbleSort(new MyComparer());