I have created a custom Circular Linked List , code given below . Now trying to implement a bubble 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 circular 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 CircularLinkedList<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);
        }
        public void AddLast(T item)
        {
            if (head == null)
                this.AddFirstItem(item);
            else
            {
                Node<T> newNode = new Node<T>(item);
                tail.Next = newNode;
                newNode.Next = head;
                newNode.Previous = tail;
                tail = newNode;
                head.Previous = tail;
            }
              count;
        }

        void AddFirstItem(T item)
        {
            head = new Node<T>(item);
            tail = head;
            head.Next = tail;
            head.Previous = tail;
        }
        public void Clear()
        {
            head = null;
            tail = null;
            count = 0;
        }
        public bool Contains(T item)
        {
            return Find(item) != null;
        }

        public Node<T> Find(T item)
        {
            Node<T> node = FindNode(head, item);
            return node;
        }

        Node<T> FindNode(Node<T> node, T valueToCompare)
        {
            Node<T> result = null;
            if (comparer.Equals(node.Value, valueToCompare))
                result = node;
            else if (result == null && node.Next != head)
                result = FindNode(node.Next, valueToCompare);
            return result;
        }


        public void CopyTo(T[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");
            if (arrayIndex < 0 || arrayIndex > array.Length)
                throw new ArgumentOutOfRangeException("arrayIndex");

            Node<T> node = this.head;
            do
            {
                array[arrayIndex  ] = node.Value;
                node = node.Next;
            } while (node != head);
        }

        public IEnumerator<T> GetEnumerator()
        {
            Node<T> current = head;
            if (current != null)
            {
                do
                {
                    yield return current.Value;
                    current = current.Next;
                } while (current != head);
            }
        }
        public bool Remove(T item)
        {
            Node<T> nodeToRemove = this.Find(item);
            if (nodeToRemove != null)
                return this.RemoveNode(nodeToRemove);
            return false;
        }

        bool RemoveNode(Node<T> nodeToRemove)
        {
            Node<T> previous = nodeToRemove.Previous;
            previous.Next = nodeToRemove.Next;
            nodeToRemove.Next.Previous = nodeToRemove.Previous;

            // if this is head, we need to update the head reference
            if (head == nodeToRemove)
                head = nodeToRemove.Next;
            else if (tail == nodeToRemove)
                tail = tail.Previous;

            --count;
            return true;
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}

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 Bubblesort like below

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

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

and initialize code

CircularLinkedList<Fund> cll = new CircularLinkedList<Fund>();
cll.BubbleSort();

but its still giving me error like At least one object must implement IComparable.

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());