Insertion Sort on a linked list

Discussion in 'Java' started by Java Newbie, Feb 4, 2007.

  1. Java Newbie

    Java Newbie Guest

    I am trying to implement an insertion sort for a doubly linked list.
    The node has an item, prev, and node.
    I have tried everything and I can't figure out why this code doesn't
    work. Please help
    Debugging this thing has been a pain. Its messes up randomly.

    public void insertionSort()
    {
    Node pointer=head;
    while(pointer.next!=null)
    {

    Node insert=pointer.next;
    if (insert.item.compareTo(pointer.item)>0)
    {
    pointer=pointer.next;
    }
    else
    {

    insert.prev.next=insert.next;
    insert.next.prev=insert.prev;
    if (head.item.compareTo(insert.item)>0)
    {
    insert.next=head;
    insert.prev=null;
    head.prev=insert;
    head=insert;


    }

    Node current = head.next;

    while(current.item.compareTo(insert.item)<0)
    {
    current=current.next;
    }
    insert.next=current;
    insert.prev=current.prev;
    current.prev.next=insert;
    current.prev=insert;
    }
    }

    }
    Java Newbie, Feb 4, 2007
    #1
    1. Advertising

  2. Java Newbie wrote:
    > I am trying to implement an insertion sort for a doubly linked list.
    > The node has an item, prev, and node.
    > I have tried everything and I can't figure out why this code doesn't
    > work. Please help
    > Debugging this thing has been a pain. Its messes up randomly.

    ....

    Your code might benefit from some comments. I'm not sure, for example,
    whether your comparisons are the right way round, but I'm not sure of
    their intent.

    Meanwhile, see http://home.earthlink.net/~patricia_shanahan/debug/ for
    an organized approach to debug.

    Patricia
    Patricia Shanahan, Feb 4, 2007
    #2
    1. Advertising

  3. Java Newbie

    Mark Space Guest

    Java Newbie wrote:
    > I am trying to implement an insertion sort for a doubly linked list.
    > The node has an item, prev, and node.
    > I have tried everything and I can't figure out why this code doesn't
    > work. Please help
    > Debugging this thing has been a pain. Its messes up randomly.


    You need to learn, in my opinion, hand execution. Hand execution means
    you play the computer, and execute the code written out on a piece of
    paper. This is the best way for a student to learn how to debug a
    program. It's crucial that you learn, because there's no way for you to
    continue writing programs unless you get this, so buckle down and just
    do it.

    On a blank piece of binder paper, start executing your code by following
    it line by line. Make sure to execute every line, and every step, and
    follow any changes in program flow (if, while, next, case, break, etc.)
    carefully. If you forget something you'll mess up.

    When you get to a new variable, write it down on the left side of the
    binder paper. Make sure to write a value for it on the right. As a
    variable changes cross out the old value, and write the new value next
    to it on the right. Make sure to leave enough space after the variable
    so you can fill in a few lines of new values.

    This is the best way to learn how to program. As you do this, you'll
    get better at "reading" code and learning to debug algorithms faster.
    You'll need to be able to work problems on paper because test problems
    don't let you use a computer. As you get even more skilled, you'll be
    able to debug programs in your head, with out the paper. You'll need
    the paper at first though because it's easier to keep track of
    everything that way.

    If I do this for you, I'd get down to the first line of code, where you
    declare a new variable of type Node called "pointer." I write down
    "pointer" on the piece of paper on the left, like this,

    pointer:

    So now I need to fill in the value for pointer. Most new variables are
    null (reference) or have their instance variables set to null or 0 when
    they are new()'d. This variable, pointer, has an assignment, so I can
    set it to the value of "head." Unfortunately, I don't see "head" on my
    piece of paper, so it's undefined. My hand execution dies there because
    I don't have enough info to continue.

    pointer: WTF?!?

    So, you need to look at your program, start from the beginning where
    "head" is defined, and get that value on your paper. Then proceed from
    there. When you feed this routine values, try to keep them short, you
    are not going to have a lot of fun marching through fifty values in the
    list just to do one insert. Try to pick values that provoke different
    behavior quickly so you can get to the root of any problem.

    When you have a short list of values on your paper that you think work,
    try them out on the computer. You'll need to print out each variable
    when it changes so you can see that it matches the ones you have crossed
    out on your paper. When you find one that's different, figure out why.
    Did the program do something unexpected? Did you skip a statement in
    your hand execution? Correct the problem on your paper or program, and
    continue, debugging each problem fully before worrying about any others.

    Once you get one simple run working, add some more runs with trickier
    data. Verify these on the paper first, then try them out to make sure
    the program does the same. Eventually, you will cover all cases and
    your program will be fully debugged.

    Good luck.

    >
    > public void insertionSort()
    > {
    > Node pointer=head;
    > while(pointer.next!=null)
    > {
    >
    > Node insert=pointer.next;
    > if (insert.item.compareTo(pointer.item)>0)
    > {
    > pointer=pointer.next;
    > }
    > else
    > {
    >
    > insert.prev.next=insert.next;
    > insert.next.prev=insert.prev;
    > if (head.item.compareTo(insert.item)>0)
    > {
    > insert.next=head;
    > insert.prev=null;
    > head.prev=insert;
    > head=insert;
    >
    >
    > }
    >
    > Node current = head.next;
    >
    > while(current.item.compareTo(insert.item)<0)
    > {
    > current=current.next;
    > }
    > insert.next=current;
    > insert.prev=current.prev;
    > current.prev.next=insert;
    > current.prev=insert;
    > }
    > }
    >
    > }
    >
    Mark Space, Feb 9, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jochus
    Replies:
    3
    Views:
    493
    Jochus
    Apr 21, 2005
  2. John N.
    Replies:
    5
    Views:
    537
    John N.
    Dec 31, 2003
  3. fool
    Replies:
    14
    Views:
    491
    Barry Schwarz
    Jul 3, 2006
  4. Julia
    Replies:
    6
    Views:
    598
    Dmitri Sologoubenko
    Aug 11, 2006
  5. joshd
    Replies:
    12
    Views:
    652
    John Carson
    Oct 2, 2006
Loading...

Share This Page