Insertion sort - swapping nodes

Question

I wrote following routine for the insertion sort in java for a doubly linked list which swap the data from the nodes to sort & it works fine. However, I am trying to figure out how to actually swap the node links to achieve the insertion sort. I tried numerous options but all are failed because since its the object reference which nodes are referencing to, changing them messes up & breaks the list. Any pointers would be appreciated.

Node class (inner class):

   private class Node {
    T data;
    Node next;
    Node prev;
}

Sort routine

   public void sort() {
    if(isEmpty()) {
        throw new RuntimeException("List is empty");
    }
    Node current = head;
    while(current != null) {
        for(Node prev=current; prev.prev != null; prev = prev.prev) {
            if(prev.data.compareTo(prev.prev.data) <= 0) {
                T tmp = prev.data;
                prev.data = prev.prev.data;
                prev.prev.data = tmp;
            }
        }
        current = current.next;
    }
}

EDIT1:

Thanks for lhuang for providing the method to swap the node. It works. The actual answer lies in the fact that Java copies and passes the reference by value, not object (refer http://www.javaworld.com/javaqa/2000-05/03-qa-0526-pass.html). So you should be passing the node swapping to other method rather than trying in the same place & hence it does not affect the rest of the nodes other than the two nodes which are to be swapped.

I modified my routine to the following

public void sort() {
    if(isEmpty()) {
        throw new RuntimeException("List is empty");
    }
    Node current = top;
    while(current != null) {
        for(Node prev=current; prev != null && prev.prev != null; prev = prev.prev) {
            if(prev.data.compareTo(prev.prev.data) <= 0) {
                swap(prev,prev.prev);
            }
        }
        current = current.next;
    }
}

One last issue in having this logic is that the current is always getting behind when swapped & same two nodes are processed twice in this logic. Is there a way to mitigate that i.e. to restore current in its original place after swap?

Answer 1

You need to update the previous and next nodes for node1 and node2 accordingly.

1, If one node is head, update head.

2, If node1 is right before node2, you couldn't just update node1.prev = node2.prev. It will introduce a circular in the list.

public void swap(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        throw new IllegalArgumentException(
                "The nodes couldn't be null");
    }

    if (node1 == node2) {
        return;
    }

    // make sure node1 is before node2
    if (node1.getPrev() == node2) {
        Node temp = node2;
        node2 = node1;
        node1 = temp;
    }

    Node node1Prev = node1.getPrev();
    Node node1Next = node1.getNext();
    Node node2Prev = node2.getPrev();
    Node node2Next = node2.getNext();

    node1.setNext(node2Next);
    if (node2Next != null) {
        node2Next.setPrev(node1);
    }

    node2.setPrev(node1Prev);
    if (node1Prev != null) {
        node1Prev.setNext(node2);
    }

    if (node1 == node2Prev) {
        node1.setPrev(node2);
        node2.setNext(node1);
    } else {
        node1.setPrev(node2Prev);
        if (node2Prev != null) {
            node2Prev.setNext(node1);
        }

        node2.setNext(node1Next);
        if (node1Next != null) {
            node1Next.setPrev(node2);
        }
    }

    if (node1 == head) {
        head = node2;
    } else if (node2 == head) {
        head = node1;
    }
}

For question 2, you can check prev before swap. If it is current, set current to prev.prev.

while(current != null) {
    for(Node prev=current; prev != null && prev.prev != null; prev = prev.prev) {
        if(prev.data.compareTo(prev.prev.data) <= 0) {
            if (prev==current) {
                current=prev.prev;
            }
            swap(prev,prev.prev);
        }
    }
    current = current.next;
}

By the way, you can also try to reduce swap operations. Since you are sorting a linked list and it is very easy to delete and insert an element. So just find out the proper place for current; delete it from original place and insert it there. Of course, you need to be careful of some details.

Answer 2

Assign the node references rather than just the data. Make sure you update the "next" and "prev" of the nodes to the left and right of both swapped nodes, as well as the swapped nodes themselves. And finally, make sure your iteration continues with the correct node after you swap.