I haven't found any information on this, how can I implement insertion sorting on a string with Linked Lists. I have been able to create the Linked List however I cannot figure out how to implement the sorting part.

I also want to be able to sort by first name and last name but first I need to figure out how to sort by the first name...

Here is what I have reached so far.

public class LinkedlistIS
    {
        public CustomerNode head;
        public CustomerNode sorted;

        public class CustomerNode
        {
            public int val;
            public string firstName;
            public string lastName;
            public CustomerNode next;

            public CustomerNode(int val, string firstName, string lastName)
            {
                this.val = val;
                this.firstName = firstName;
                this.lastName = lastName;
            }

            public string FirstName
            {
                get { return firstName; }
            }

            public string LastName
            {
                get { return lastName; }
            }

            public int CompareTo2(CustomerNode another)
            {
                if (this.lastName.CompareTo(another.LastName) < 0)
                    return -1;
                else
                    if (this.lastName.CompareTo(another.LastName) == 0)
                    return this.firstName.CompareTo(another.FirstName);
                else
                    return 1;
            }

        }

        public void push(int val, string firstName, string lastName)
        {
            /* allocate node */
            CustomerNode newnode = new CustomerNode(val, firstName, lastName);
            val = 1;

            /* link the old list off the new node */
            newnode.next = head;

            /* move the head to point to the new node */
            head = newnode;
        }


        // function to sort a singly 
        // linked list using insertion sort
        public void insertionSort(CustomerNode headref)
        {
            // Initialize sorted linked list
            sorted = null;
            CustomerNode current = headref;

            // Traverse the given 
            // linked list and insert every
            // node to sorted
            while (current != null)
            {
                // Store next for next iteration
                CustomerNode next = current.next;

                // insert current in sorted linked list
                sortedInsert(current);

                // Update current
                current = next;
            }

            // Update head_ref to point to sorted linked list
            head = sorted;
        }

        /*
        * function to insert a new_node in a list. Note that 
        * this function expects a pointer to head_ref as this
        * can modify the head of the input linked list 
        * (similar to push())
        */
        public void sortedInsert(CustomerNode newnode)
        {
            /* Special case for the head end */
            if (sorted == null || sorted.val >= newnode.val)
            {
                newnode.next = sorted;
                sorted = newnode;
            }
            else
            {
                CustomerNode current = sorted;

                /* Locate the node before the point of insertion */
                while (current.next != null &&
                        current.next.val < newnode.val)
                {
                    current = current.next;
                }
                newnode.next = current.next;
                current.next = newnode;
            }
        }

        /* Function to print linked list */
        public void printlist(CustomerNode head)
        {
            while (head != null)
            {
                Console.Write(head.firstName   " "   head.lastName   " "   head.val   " ");
                head = head.next;
            }
        }

Any help would be greatly appreciated.

Thanks

CodePudding user response：

There are some apparent issues:

if (this.lastName.CompareTo(another.LastName) < 0)
     return -1;
else
     if (this.lastName.CompareTo(another.LastName) == 0)
           return this.firstName.CompareTo(another.FirstName);

Why are you starting by comparing lastnames if you wanted to primarily sort by firstname?

sorted.val >= newnode.val

Why are you sorting by a value if you wanted to sort by name? Just call your comparison function if you want to compare nodes by the first/last name.

The rest of the code looks ok for a learning exercise as far as I can see. If you have issues I would recommend to

1. Write unit tests! It becomes much easier to find bugs when you can run several sets of test-data to your algorithm designed to find various edge cases. Especially for something like sorting where it is trivial to verify your result.
2. Learn how to use the debugger. The behavior of the program becomes much easier to understand when you can stop at various points and verify that the variables match your expectation.

See How to debug small programs for more details.

Writing code like this can be very useful as a learning exercise, but please do not use code like this for anything serious. There is perfectly fine sorting functions built into the framework that will be both faster and easier to understand. Also note that linked lists are rarely used in real life, I do not think I have used one even once outside of school. See also we must avoid linked lists.