Thread: Insertion Sort with Linked Lists

  1. #1
    Registered User
    Join Date
    Oct 2011

    Insertion Sort with Linked Lists

    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;

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    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())
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion Sort and Linked List
    By dlwlsdn in forum C Programming
    Replies: 2
    Last Post: 01-25-2010, 11:25 PM
  2. doubly linked lists insertion
    By bazzano in forum C Programming
    Replies: 6
    Last Post: 04-27-2007, 09:31 AM
  3. Help with Insertion sort on a single linked list
    By goron350 in forum C++ Programming
    Replies: 4
    Last Post: 07-11-2005, 08:38 PM
  4. Linked List Insertion Sort
    By The Brain in forum C++ Programming
    Replies: 4
    Last Post: 04-04-2005, 07:20 PM
  5. Radix Sort, Strings, and Linked Lists
    By dark paladin in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 03:24 PM