aspose file tools*
The moose likes Beginning Java and the fly likes selection sort in a linked list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "selection sort in a linked list" Watch "selection sort in a linked list" New topic
Author

selection sort in a linked list

Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
here are my classes...









ok, in the class NumberList, im having trouble even knowing how to do
and selection sort. because you cant just switch the two nodes, you have
to make there pointer point all crazy.

because say i have a linked list like so:

5 3 2 4 1;

current would be 5 and current2 would eventually be 1;

then 1 would have to point to 3, 4 would have to point to 5, and 5 be null;

so would it be...


or something like that, because when current increments to 3, current-1 = 1

and 1 will have to point to 2.

but can you even do current - 1, because if you can the nodes dont switch,
they just change pointers, so current - 1 might still be 5..

please help im super confused..

-Justin-


You down with OOP? Yeah you know me!
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Instead of switching around pointers, why not just exchange the contents of the two nodes?
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
so ....

int temp = current.getValue();
current = current2.getValue();
current2 = temp;

??

something like that?

never thought of that really...

ill try it

thanks,
Justin
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Well you will probably want to put setter methods in the class definition of the node to make the modification of the contents encapsulated with the rest of the class definition.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
hmm...

well is this valid syntax for a linked list?



because my prof. was using.. getValue() like it was a predefined method

of a list.

and when you say setter methods... set what?

each node is set.

as a different number, and having the next.

-Justin-
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
A method call should not appear on the left-hand side of an assignment statement the way you have it. You would call the method and send parameters.

Also I think you should recheck the logic in your loop. It looks like you are checking out the remainder of the list and then putting the minimum value found in the current node, without keeping track of what other node contained that minimum.

Also you never reset current2.

A setter method is normally a public method in a class definition that allows access from the outside to set the value of private members of the class definition. If there is only one way for another class to change the value of the data inside the class, it makes it easier to diagnose problems.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok in the code above, in the main class i created a NumberList object.

so therefore...

current.next, and current.number, won't work because .next and .number can

only be used by NumberNode and it's variables.

and i want to create a method called



but im not sure what to pass, because i can't pass a NumberList object,

because i won't be able to sort through it with .next and .number.

but i cant pass a Node either, because a node is just one object in the list

and i need to have a list passed.

could i pass this:



but the thing is..

what ever i pass i need to make the private NumberNode list equal that

list object that is passed..

i super need help,

thanks,
Justin
[ May 01, 2006: Message edited by: Justin Fox ]
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Originally posted by Justin Fox:
[QB]ok in the code above, in the main class i created a NumberList object.

so therefore...

current.next, and current.number, won't work because .next and .number can

only be used by NumberNode and it's variables.


If current is an instance of a NumberNode, then you can access the variables next and number, but its better to make them private variables and access their values through getter methods.

and i want to create a method called



It might be easier for you to start with the pseudocode for Selection Sort and figure out how you would modify it to use with a NumberList.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok i fixed my code...

here are the three classes...







all I'm getting now is a:

Exception in thread "main" java.lang.NullPointerException
at ListMain.main(ListMain.java:37)


I don't know why either, please help me out!

thanks
-Justin-
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Well the only reason you break out of the inner while loop is if current2 is null. You can't access the variable value on current2 after that loop.

Also you need to look again at the logic.

Also you don't reset current2.
[ May 01, 2006: Message edited by: Keith Lynn ]
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok, how do I get current2 to remember where 1 is? because after the loop, current2 is null.

because in an array, you can do array[min], but not in a linked list...

thanks

-Justin-
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
anyone have any pointers to get me in the right direction?

that would be gggggreat!..

thanks,
Justin
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
One suggestion I have is to try to emulate how the Selection Sort works for an array of ints.

At the start you have current pointing to the first node in the list. Then let current2 point to the next node in the list (if there is one), and from that point on, compare the contents of the node pointed to by current and the node pointed to by current2 and swap if necessary. After current2 has examined all the nodes in the list, you know the minimum is in the node pointed to by current.

So you then move current forward and repeat.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
sweet, i figured it out,

i had to put the swap in the inner loop, so it would swap the lesser value

each time it found one;

and i had to put "current2 = current.next;"

in the outer for loop, so it would update current2 every loop around

thanks again,

-Justin-
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: selection sort in a linked list