Insertion Sort Doubly Circular Linked List

Question

So I'm trying to get my Doubly Linked List to do an insertionSort

I'm having issues right now with just moving the nodes to their proper spot. I have gotten comparisons working but none of my nodes move.

public void insertionSort()
{
    Node temp;
    Node start = this.head.next;
    Node next = start.next;
    Node prev = this.head;

    while(start != this.head)
    {
        if(start.data.compareTo(next.data) > 0) //start is larger than next
        {
            temp = start;
            start = next;
            next = temp;
        }
        start = start.next;
        next = next.next;
        prev = prev.next;
    }
}

I was wondering if someone could help me in getting this algorithm right. I'm using a circular doubly linked list to try and test various sort routines for time complexity.

Answer 1

Fun puzzle!

The main problem I can see with your algorithm is that you only give the node being inserted the opportunity to move one place back.

Insertion sort looks from the second node in a list to the last one by one, swapping them backward until they are sorted in the preceding already sorted list. That might take several swaps, but your algorithm only allows for one (when your if condition is true) or zero (when it's false). For example, say we are sorting:

b c a

Your insertion sort would work when start is at b and c, then it would move to a. Here you say 'if a is before c, swap it with c', giving:

b a c

...but then your algorithm would terminate. Since there are an undetermined number of swaps you need to do for each node being inserted, you need another while loop there. Here is the pseudocode for an insertion sort algorithm:

function insertion_sort(items) {
    while (i=1; i < items length; i++) { // for elements 1 to n
        while (j=i; j >= 0; j--) { // look backward through all previously sorted items
            if (items element at j < items element at j-1) {
                 swap element at j with element at j-1
            } else {
                break out of the loop
            }
        }
    }
}