Reference-Based Selection Sort
I'm having problems doing a selection sort with a linked list (not a doubly linked list). I have a class called OrderedList that extends a class called List. In my sort method, I try to make a new OrderedList to put the smallest nodes, one by one, into it. I try to remove the smallest node from the old list so that it can find the next smallest with the next pass. Anyways, I keep getting null errors and such...here is my sort method of my OrderedList class.
public Node sort(Node someHead){
Node n1 = someHead;
Node current = null;
Node smallest = someHead;
Node nodeA;
Node beforeSmallest=null;
Node current2;
OrderedList collection2 = new OrderedList();
for(current2=head; current2.getNext()!=null; current2=current2.getNext()){
// Find the node with the smallest element
for (current = n1.getNext(); current.getNext()!=null; current= current.getNext()){
// If "smallest" has a larger element than "current,"
// "smallest" is not actually the smallest element.
// This assignment fixes that.
if (smallest.getElement().compareTo(current.getElement())>0)
smallest = current;
}
// Add that "smallest" element to a new list
collection2.add((Comparable)(smallest.getElement()));
// Find the node just before the smallest node
// As long as "smallest" isn't at the head, find the node located
// before it.
if (smallest!=head){
for (nodeA=head; nodeA.getNext()==smallest; nodeA=nodeA.getNext())
beforeSmallest=nodeA;
// Overwrite the smallest node by setting beforeSmallest's next
// node to be the node after smallest
beforeSmallest.setNext(smallest.getNext());
}
// if the smallest node is at the head of the list, then get rid of it
// by setting the next node to be the head.
else
head=smallest.getNext();
}
// return the sorted list
return collection2.head;
}
Can anyone give me some help with this? If you need more information about my implementation or my classes or methods let me know. Thanks for any advice.
