asked on

Selection sort for linked list

Hey, Im writing a selectionSort method for a circular doubly linked list. I posted the code below, but I got something wrong because it gets stuck in an infinit loop and doesnt do anything.... So my logic must be bad somewere. I have it built into my LinkedList class so thats why there arnt any parms coming in and why I can refer to fields in the sort directly. It compiles fine so no compileling errors just the infinit loop.
Thanks

public void selectionSort()//built into LinkedList class so dont need parms
		{
			Node curPos;
			Node indexSmallest; 
			Node start;
			Node temp;
			for (start = this.head, curPos = this.head.next; start != null; )
			{
				indexSmallest = start;
				for (curPos = start, curPos = this.head.next; curPos != null; )
				{
					if (indexSmallest.compareTo(curPos) > 0)
					{
						indexSmallest = curPos;
					}
				} // end for
				temp = start;
				start = indexSmallest;
				indexSmallest =  temp;
			} // end for       
		}

Open in new window

Mick Barry

> start = indexSmallest;

looks like that should be:

start = curPos;

Mick Barry

and you don't actually do a swap, all you change is local vars. You need to instead swap the data attached to the nodes

theldro

ASKER

I changed the part you said, Im sure that was a problem too, but the sort gets stuck in the infinit loop before that I think. I think the problem might be that I have a bad comparTo() method. The comparTo() method works fine for my BubbleSort, but I think its a problem for selection sort. Im not sure though so heres the method. I feel like a retard asking all these questions, sorry if they sound stupid.
Thanks

public class DLL implements Comparable<Node>//implementing comparable interface.
{
....

        public int compareTo(Node that) 
        {
        return ((Comparable)this.head).compareTo((Comparable)   that.data);
        }
			
			
			
}

Open in new window

ASKER CERTIFIED SOLUTION

Mick Barry

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

theldro

ASKER

Thanks for helping me so much