3

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;
            }
        }
    }
AstroCB
  • 12,337
  • 20
  • 57
  • 73
Aaron
  • 117
  • 1
  • 2
  • 7

6 Answers6

4

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).

Carl Smotricz
  • 66,391
  • 18
  • 125
  • 167
  • 1
    "compareToIgnoreCase(String str)" This is exactly the solution to my problem. Unfortunately, I wasn't paying attention that some of my test data were mixed upper and lower cases...I can't believe I overlooked something so simple. Also, I did change the comparison to "> 0" to put in ascending order, thanks! – Aaron Dec 06 '09 at 17:05
  • 1
    Oh good, my perseverance paid off. Oh wait, it didn't: No accept, no upvote. No flowers either, and I bet you won't even call me! * sniff * – Carl Smotricz Dec 06 '09 at 17:15
  • 1
    Heh, forget to accept...I don't have flowers, but I recently inherited a lot of candy :3 – Aaron Dec 06 '09 at 17:28
0

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.

Carl Smotricz
  • 66,391
  • 18
  • 125
  • 167
  • Yes, that would probably be the easiest way of doing this, although I guess for my own satisfaction I'd like to be able to know how to resort the nodes themselves. – Aaron Dec 06 '09 at 17:16
0

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

pstanton
  • 35,033
  • 24
  • 126
  • 168
  • 3
    Quote: "I'm implementing my own linked list in Java." This is a learning exercise, which wouldn't be fulfilled by using the canned APIs. – Carl Smotricz Dec 06 '09 at 09:38
  • the question doesn't state that it's a learning exercise or that 'canned' api's shouldn't be used. that is your interpretation. – pstanton Dec 06 '09 at 09:42
  • 1
    my interpretation is that it's a learning exercise too. Otherwise, he wouldn't need to implement a linked list. – b.roth Dec 06 '09 at 12:01
  • @Bruno - he may *think* he needs to implement linked lists. – Stephen C Dec 06 '09 at 13:29
  • This would be a lot easier if the asker hadn't left us so alone with the question. – Carl Smotricz Dec 06 '09 at 13:49
  • This program is an exercise a friend of mine is having to do for his class, and so I decided to try it as well (since I need to work on my data structure ability). So, although I'm familiar with the Java Collections library I am restricting myself from them for everything, including sorts. Thanks for the suggestion though. Also, sorry I haven't replied sooner but I have to sleep sometime ;) – Aaron Dec 06 '09 at 17:08
0

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.

Community
  • 1
  • 1
sergtk
  • 10,714
  • 15
  • 75
  • 130
  • Yes, there are certainly better sorts out there than bubble sort, but I think having O(n^2) for runtime is not so bad for the small input I'm testing it with (~50 entries). Plus, sorting is done 'in place' and so I don't have to allocate for more space when doing a 'merge' process. Perhaps later on I will implement a fast sorting algorithm though, thanks for the suggestion. – Aaron Dec 06 '09 at 17:13
  • @Aaron If you have only 50 items bubble sort is ok, it would be good if you update the question. Concerning allocation, I would like to pay your attention that for good implementation of merge sort on _lists_ extra allocations do NOT required. (In contrast in case of arrays allocations are needed). – sergtk Dec 06 '09 at 17:34
0

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

WarmWaffles
  • 531
  • 5
  • 16
  • Thanks for the thoughts. I'm doing this as an exercise in data structures, so I wanted to avoid any use of extra arrays and stick just to the list itself. I had first tried to put things in order upon the insert function, but I was finding it difficult to iterate through the list while at the same time change the list. For instance, this is what my iteration looked like: Node temp = head; while (temp != null; // do something here temp = temp.link; } I could find an 'index' of where to insert the node, but as far as applying the changes to the head node itself, I couldn't figure it out :( – Aaron Dec 06 '09 at 17:24
0

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

}

Bhumik Thakkar
  • 65
  • 1
  • 1
  • 3