This week's book giveaway is in the Java in General forum.
We're giving away four copies of Think Java: How to Think Like a Computer Scientist and have Allen B. Downey & Chris Mayfield on-line!
See this thread for details.
Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

selection sort in a linked list

 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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-
 
Keith Lynn
Ranch Hand
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Instead of switching around pointers, why not just exchange the contents of the two nodes?
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
anyone have any pointers to get me in the right direction?

that would be gggggreat!..

thanks,
Justin
 
Keith Lynn
Ranch Hand
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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-
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic