Insertion Sort on a linked list
 

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;
}
}

}

Re: Insertion Sort on a linked list
 

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

Re: Insertion Sort on a linked list
 

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;
> }
> }
>
> }
>