Insertion Sort with Linked Lists

[Linell Bonnette]

The code I have isn't right, and I know it. However, I've spent a few hours on this and don't know what else to do. I know the basics of insertion sort, but linked lists confuse me.

In other words, I know the theory. How do I actually apply it? This is the code for insertion sort that I have (I'm using a dummy node for head).

for (cursor = head->rlink(); cursor != NULL; cursor = cursor->rlink()) {
        cursor2 = cursor;
        while (cursor2->rlink() != NULL && cursor2->rlink()->value > cursor->value) { 
            cursor2 = cursor2->rlink();    // maybe llink?
        }
        Node *temp;
        temp = cursor;
        cursor2->set_llink(cursor->llink());a
        temp->set_llink(cursor2->rlink());
    }

[iMalc]

One way to solve the problem is to break it down into smaller chunks.
For example, this code takes an unsortedList, empties that out, and places all the items in sorted order into sortedList. In other words, it performs a full insertion sort, but requires you to code the functions that are missing.

while (!unsortedList.empty())
    sortedList.insert(unsortedList.pop_front());

And of course afterwards you can just swap the sorted and unsorted list contents to get it all back into the original list.

So you now have three smaller sub-problems to solve: empty, insert, and pop_front. Whether you're doing a singly-linked or doubly-linked list, this will simplify things for you to the point where you might be able to solve it on your own I expect.