Manually sorting a linked list in Java (lexically)

Question

I am implementing my own linked list in Java. The node class merely has a string field called "name" and a node called "link". Right now I have a test driver class that only inserts several names sequentially. Now, I am trying to write a sorting method to order the nodes alphabetically, but am having a bit of trouble with it. I found this pseudocode of a bubblesort from someone else's post and tried to implement it, but it doesn't fully sort the entries. I'm not really quite sure why. Any suggestions are appreciated!

    private void sort()
    {
        //Enter loop only if there are elements in list
        boolean swapped = (head != null);

        // Only continue loop if a swap is made
        while (swapped)
        {
            swapped = false;

            // Maintain pointers
            Node curr = head;
            Node next = curr.link;
            Node prev = null;

            // Cannot swap last element with its next
            while (next != null)
            {
                // swap if items in wrong order
                if (curr.name.compareTo(next.name) < 0)
                {
                    // notify loop to do one more pass
                    swapped = true;

                    // swap elements (swapping head in special case
                    if (curr == head)
                    {
                        head = next;
                        Node temp = next.link;
                        next.link = curr;
                        curr.link = temp;
                        curr = head;
                    }
                    else
                    {
                        prev.link = curr.link;
                        curr.link = next.link;
                        next.link = curr;
                        curr = next;
                    }
                }

                // move to next element
                prev = curr;
                curr = curr.link;
                next = curr.link;
            }
        }
    }

Answer 1

I spent some minutes eyeballing your code for errors but found none.

I'd say until someone smarter or more hard working comes along you should try debugging this on your own. If you have an IDE like Eclipse you can single-step through the code while watching the variables' values; if not, you can insert print statements in a few places and hand-check what you see with what you expected.

---

UPDATE I

I copied your code and tested it. Apart from the fact that it sorts in descending order (which may not be what you intended) it worked perfectly for a sample of 0, 1 and 10 random nodes. So where's the problem?

UPDATE II

Still guessing what could be meant by "it doesn't fully sort the entries." It's possible that you're expecting lexicographic sorting (i.e. 'a' before 'B'), and that's not coming out as planned for words with mixed upper/lower case. The solution in this case is to use the String method compareToIgnoreCase(String str).

Answer 2

This may not be the solution you're looking for, but it's nice and simple. Maybe you're lazy like I am.

Since your nodes contain only a single item of data, you don't really need to re-shuffle your nodes; you could simply exchange the values on the nodes while leaving the list's structure itself undisturbed.

That way, you're free to implement Bubble Sort quite simply.

Answer 3

you should use the sorting procedures supplied by the language.

try this tutorial.

Basically, you need your element class to implement java.lang.Comparable, in which you will just delegate to obj.name.compareTo(other.name)

you can then use Collections.sort(yourCollection)

alternatively you can create a java.util.Comparator that knows how to compare your objects

Answer 4

To obtain good performance you can use Merge Sort. Its time complexity is O(n*log(n)) and can be implemented without memory overhead for lists.

Bubble sort is not good sorting approach. You can read the What is a bubble sort good for? for details.

Answer 5

This may be a little too late. I would build the list by inserting everything in order to begin with because sorting a linked list is not fun.

I'm positive your teacher or professor doesn't want you using java's native library. However that being said, there is no real fast way to resort this list.

You could read all the nodes in the order that they are in and store them into an array. Sort the array and then relink the nodes back up. I think the Big-Oh complexity of this would be O(n^2) so in reality a bubble sort with a linked list is sufficient

Answer 6

I have done merge sort on the singly linked list and below is the code.

public class SortLinkedList {

public static Node sortLinkedList(Node node) {

    if (node == null || node.next == null) {
        return node;
    }
    Node fast = node;
    Node mid = node;
    Node midPrev = node;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        midPrev = mid;
        mid = mid.next;
    }
    midPrev.next = null;
    Node node1 = sortLinkedList(node);
    Node node2 = sortLinkedList(mid);
    Node result = mergeTwoSortedLinkedLists(node1, node2);
    return result;
}

public static Node mergeTwoSortedLinkedLists(Node node1, Node node2) {
    if (null == node1 && node2 != null) {
        return node2;
    } else if (null == node2 && node1 != null) {
        return node1;
    } else if (null == node1 && null == node2) {
        return null;
    } else {

        Node result = node1.data <= node2.data ? node1 : node2;
        Node prev1 = null;
        while (node1 != null && node2 != null) {
            if (node1.data <= node2.data) {
                prev1 = node1;
                node1 = node1.next;
            } else {
                Node next2 = node2.next;
                node2.next = node1;
                if (prev1 != null) {
                    prev1.next = node2;
                }
                node1 = node2;
                node2 = next2;
            }
        }
        if (node1 == null && node2 != null) {
            prev1.next = node2;
        }
        return result;
    }
}

public static void traverseNode(Node node) {
    while (node != null) {
        System.out.print(node + "  ");
        node = node.next;
    }
    System.out.println();

}

public static void main(String[] args) {
    MyLinkedList ll1 = new MyLinkedList();

    ll1.insertAtEnd(10);
    ll1.insertAtEnd(2);
    ll1.insertAtEnd(20);
    ll1.insertAtEnd(4);
    ll1.insertAtEnd(9);
    ll1.insertAtEnd(7);
    ll1.insertAtEnd(15);
    ll1.insertAtEnd(-3);
    System.out.print("list: ");
    ll1.traverse();
    System.out.println();
    traverseNode(sortLinkedList(ll1.start));

}

}

The Node class:

public class Node {
int data;
Node next;

public Node() {
    data = 0;
    next = null;
}

public Node(int data) {
    this.data = data;
}

public int getData() {
    return this.data;
}

public Node getNext() {
    return this.next;
}

public void setData(int data) {
    this.data = data;
}

public void setNext(Node next) {
    this.next = next;
}

@Override
public String toString() {
    return "[ " + data + " ]";
}

}

The MyLinkedList class:

public class MyLinkedList {
Node start;

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (start == null) {
        start = newNode;
        return;
    }
    Node traverse = start;
    while (traverse.getNext() != null) {
        traverse = traverse.getNext();
    }
    traverse.setNext(newNode);
}

public void traverse() {
    if (start == null)
        System.out.println("List is empty");
    else {
        Node tempNode = start;
        do {
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.getNext();
        } while (tempNode != null);
        System.out.println();
    }
}

}