sort method

[minimi]

Here is my code: http://pastebin.com/KTR86nzD

This is input.csv:
name,age
Fred,88
Stella,11
Nellie,99
George,22
Violet,33
Rose,77
Bob,66
Lena,55
Billy,44

It should print the above in this format -
Fred is 88 years old
Stella is 11 years old
Nellie is 99 years old
...
Billy is 44 years old.

Afterwards, it should sort the age in ascending order and print them like this
Stella is 11 years old
George is 22 years old
Violet is 33 years old
...
Nellie is 99 years old.

Also when output is printed, first line is always
name is years old.
Is there way to get rid of this?

I think my bubbleSort() method is wrong. Could anyone help me out?

[apines]

First, notice that you are handling objects, which are by reference. The code

PersonNode temp = current;

Means that temp points to the location in the heap of current - changes that you are making for current will also affect temp! You will have to copy the object using a copy constructor or simply hold the instance members in different variables (hold int age for the age etc').

Also - you never change swap, it is always false, so I don't understand what you are doing with it in the bubble sort.

[minimi]

public void bubbleSort() {
         boolean swap = false; // default boolean value
         for (PersonNode i = head; i != null; i = i.getNext()) {
            swap = false;
            for (PersonNode current = head; current != null; current = current.getNext()) {
               if (current.equals(current.getAge())) {
                  PersonNode temp = current;
                  PersonNode age2 = current.getAge();
                  PersonNode name2 = current.getName();
                  PersonNode next = current.getNext(); 
                  next.age = temp.getAge();
                  next.name = temp.getName();
               }
            }
            if (!swap) {
               swap = true;
            }
         }

[kramerd]

Here's an example of bubble sort on an array of int's copied from this web page.

private void bubbleSort(int[] unsortedArray, int length) {
      int temp, counter, index;

      for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array.
         for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter.
            if(unsortedArray[index] > unsortedArray[index+1]) { //Test if need a swap or not.
               temp = unsortedArray[index]; //These three lines just swap the two elements:
               unsortedArray[index] = unsortedArray[index+1];
               unsortedArray[index+1] = temp;
            }
         }
      }
   }

I don't think you need the boolean variable swap, but you do need to compare if one person's age is greater than or less than another's to determine whether you need to swap. Also, the code you have to swap 2 nodes doesn't look right.

[minimi]

I'm kind of confused here.. am I supposed to getAge() of current and next so I could compare these two values or getNext().age? I've been trying for long time with not much progress..

[kramerd]

You are trying to compare one element's age with the next element's age. This means you should compare current.getAge() with current.getNext().getAge() .

[minimi]

public void bubbleSort() {
         Integer num1 = new Integer(0);
         Integer num2 = new Integer(0);
         for (PersonNode i = head; i != null; i = i.getNext()) {
            for (PersonNode current = head; current != null; current = current.getNext()) {
               num1 = Integer.parseInt(current.getAge()); // add to the end of the list
               num2 = Integer.parseInt(current.getNext().getAge()); // current getNext() new name and age from PersonNode
            }
         }
      }

[minimi]

Here is the full revised code:
http://pastebin.com/iXTptntF

[kramerd]

OK. So you have current's age in num1 and next's age in num2. That's a good start. Now, what do you need to do with those? Look again at the integer bubble sort algorithm I posted. Hopefully that will help.

[minimi]

But the problem is the rest of the name and age variables on this code are in String data type so it throws an error after it displays first JOptionPane. I tried changing it to Integer for hours but I couldn't figure it out so I stayed with String.

You can't compare String data type's number to see which one is bigger right? So I used parseInt but I guess it's not going to work.

public void bubbleSort() {
         Integer num1 = new Integer(0);
         Integer num2 = new Integer(0);
         Integer temp = new Integer(0);
         for (PersonNode i = head; i != null; i = i.getNext()) {
            for (PersonNode current = head; current != null; current = current.getNext()) {
               num1 = Integer.parseInt(current.getAge()); // add to the end of the list
               num2 = Integer.parseInt(current.getNext().getAge()); // current getNext() new name and age from PersonNode
            }
            
            if(num1 > num2) {
               temp = num1;
               num1 = num2;
               num2 = temp;
               // num1.toString();
               // num2.toString();
            }
         }
      }
   } // end of LinkedList()

[kramerd]

First, your if statement on line 11 has to come before the close curly brace on line 9. In other words, it needs to be inside the for loop that starts on line 6.

Second, the condition in your if is correct, but your swap isn't right of course. The condition in English says, if current's age is greater than next's age. So what do you need to do if that is the case?

You need to swap current and current.next. Do you know how to do that? Try drawing a picture of a linked list with 4 or 5 elements. Choose two nodes in the middle of the list and see what it would take to swap their positions in the list.

[apines]

kremerd is right - drawing is very helpful. I will try to help you out with the pictures. We will do together one scenario, you will try and translate into code. The rest of the scenarios will be easier then I believe. Let's have this linked list:

We want to swap node1 and node2, meaning that the list should go head [TEX]\rightarrow[/TEX] node2[TEX]\rightarrow[/TEX] node1[TEX]\rightarrow[/TEX] the rest of the list as usual. First thing let's change node2.next() so it will point to next1, the next in line in the new order:

Now, node1.next() should point to where node pointed before, because now this is his new place in the list:

And eventually we need head, who pointed at node1, to point now at node2:

Now, note that you need not to "lose" your nodes, for example after changing node2.next() to point to node1, we make the older node2.next() unreachable:

We can make a temp node that will point to node2.next() before changing it to node1:

You need to be sure that during the entire swap you don't lost any nodes.

This was one swap scenario - can you think about more scenarios that you need to check and handle as part of the swap?

[minimi]

I followed apine's diagram.. I'm not sure if it's correct but I think it stops after first JOptionPane because num1 and num2 aren't String data type.

public void bubbleSort() {
         Integer num1 = new Integer(0);
         Integer num2 = new Integer(0);
         Integer temp = new Integer(0);
         for (PersonNode i = head; i != null; i = i.getNext()) {
            for (PersonNode current = head; current != null; current = current.getNext()) {
               num1 = Integer.parseInt(current.getAge());
               num2 = Integer.parseInt(current.getNext().getAge());
               
               if(num1 > num2) {
                  num1 = num2;
               	temp = num1;
               	num2 = temp;
                  num1.toString();
                  num2.toString();
               }
            }
         }
      }

[kramerd]

I'm not sure what you're talking about: I don't see any JOptionPane here. I also don't see that you are trying to swap the nodes in your list according to apines' diagram. And why are you converting num1 and num2 to strings?

[minimi]

I meant in the main method. When I run the program, it prints the first JOptionPane, then it prints error JOptionPane "ERROR: For input string: "age"" instead of sorted JOptionPane.

I tried creating new PersonNode x, for example - PersonNode x = current.getAge() PersonNode y = current.getNext().getAge(), but it won't compile. I'm not too sure what you mean by swapping the node. Didn't I swap num1, num2, and temp accordingly?

[apines]

When you do PersonNode x = current.getAge() you are trying to insert an int into a variable that can store PersonNode. The correct syntax should be PersonNode = current - that states that x, which is a PersonNode, points to the same place in the heap that current is pointing to. After that, doing x.getAge() is the same as current.getAge() , and doing node.next = x is the same as node.x = current .
If I have confused you, or you don't know what is the heap, tell me and I will explain it to you :) There is a big difference between trying to swap primitive types such as int, boolean, char etc' to objects, which are by reference in Java such as your PersonNode.

[minimi]

I can't seem to figure out the if condition to check if v1 is greater than v2? Am I closer now? Now, it prints NullPointerException after it prints first JOptionPane on main method.

I know if condition is wrong but is the swap correct at least?

public void bubbleSort() {
         //Integer num1 = new Integer(0);
         //Integer num2 = new Integer(0);
         //Integer temp = new Integer(0);
         for (PersonNode i = head; i != null; i = i.getNext()) {
            for (PersonNode current = head; current != null; current = current.getNext()) {
               PersonNode temp;
               PersonNode v1 = current;
               PersonNode v2 = current.getNext();
               v1.getAge();
               v2.getNext().getAge();
               //num1 = Integer.parseInt(current.getAge());
               //num2 = Integer.parseInt(current.getNext().getAge());
               
            	if(v1.equals(v2) > 0) {
                  temp = v1;
                  v1 = v2;
                  v2 = temp;   
            	}
            	
               /*
               if(v1.compareTo(v2) > 0) {
                  num1 = num2;
                  temp = num1;
                  num2 = temp;
                  num1.toString();
                  num2.toString();
               }
               */
            }
         }

[apines]

Take a look at the equals method - public boolean equals(Object obj) . This method only gives true or false depending on whether the two objects are equal to one another. In this case - if they are the same object. You want to check the age variable in both nodes, and not just if they are equal - if they are bigger, equal or smaller - I think the compareTo method is better for that purpose :)

[kramerd]

The code you had before with num1 and num2 was better. I told you before that you had the condition in that code correct, but you were not swapping the nodes correctly.

In order to swap the nodes, you must do something like the diagram that apines' showed and tried to explain to you.

Remember when you declare a variable and make an assignment, the type of the variable on the left hand side must match the value you are trying to assign on the right hand side. Here are some examples.

Integer num1 = Integer.parseInt(current.getAge());   // either this or the next line are correct
int num1 = Integer.parseInt(current.getAge());       // since getAge() returns an int
PersonNode v1 = current;  // this makes another reference to the same object
// the next one doesn't work because the type of the variable is PersonNode, but the value on the right is an int
PersonNode v2 = current.getAge();  // ERROR!

To swap two nodes in a linked list, you have to deal with references to the nodes. They are currently linked together in a particular way, and you have to change that so they end up linked together in a different way. apines' diagram was trying to show how to do that.

The first picture in the diagram shows what the list looks like before any changes. The second picture shows that node2's next pointer needs to point to node1. So if I had references to nodes 1 & 2, I would make this change like this:

node2.next = node1;

The next picture shows that node1's next needs to point to node2's old next. Here's where you have to be careful that you don't lose node2's old next. So I would change the code above to something like this:

PersonNode temp = node2.next;  // do this so you don't lose the reference to node2's old next.
node2.next = node1;
node1.next = temp;

This is not all that needs to be done, but it's a start. Hopefully you now understand what the diagram is showing you and you can complete the rest.

[apines]

Try to do one swap as showed in the diagram and as kramerd elaborated, and than think about special cases that need your attention, such as what if the length of the linked list is 1, or 2?

[minimi]

I updated the full - revised code: http://pastebin.com/bVWRLQdv
Other than the nodes being swapped correctly, will this work because both name and age variables are in String? I tried to change age to Integer but my codes become uncontrollable at that point - I tried fixing it for hours without solutions.

public void bubbleSort() {
         Integer num1 = new Integer(0);
         Integer num2 = new Integer(0);
         
         for (PersonNode i = head; i != null; i = i.getNext()) {
            for (PersonNode current = head; current != null; current = current.getNext()) {
               num1 = Integer.parseInt(current.getAge());
               num2 = Integer.parseInt(current.getNext().getAge());
               PersonNode node1 = current;
               PersonNode node2 = current.getNext();
               PersonNode tempNode;
               
               if(node1.compareTo(node2)) {
                  tempNode = node2.next;
                  node2.next = node1;
                  node1.next = tempNode;
                  head = node2;
                  node2.next = node1;
                  tempNode = node2.next;
                  node2 = node1.next;
               }
            }
         }
      }

[kramerd]

1. The if statement on line 13 should be comparing num1 and num2, not node1 and node2.
2. the code inside the if is fine up to line 17. At this point you get into trouble.

You can't just blindly assign head to equal node2. What if there are 100 nodes in the list, and node2 is the 50th and node1 is the 49th?

The code on lines 18-20 doesn't make any sense.

[apines]

I think at line 17 my drawing from before confused you - you cannot assume that head is the node that you need to change. You need to change the element that is before the first element that you are trying to swap. As kramerd said - if node1 is the 49th and node2 is the 50th, you will have to change the (node 48th).next to point at node2, and you will not touch head during the entire swap process. I suggest that you draw the drawing again, using different places for the nodes - at the head, tail and in the middle, to be sure that you are not stuck on only one scenario.

[minimi]

So

if(num1 > num2) {

is correct? If I assumed correctly, we're only using Integer num1 and num2 to compare in if statement, but using node1 and node to swap? Am I on the right track in terms of swapping goes (I know the swap is wrong but I just wanted to know if I'm on right track). Thanks!

[kramerd]

Yes, yes, yes! You are using num1 and num2 to compare the ages, but you need to swap the nodes. :)

[apines]

So

if(num1 > num2) {

is correct? If I assumed correctly, we're only using Integer num1 and num2 to compare in if statement, but using node1 and node to swap? Am I on the right track in terms of swapping goes (I know the swap is wrong but I just wanted to know if I'm on right track). Thanks!

You are definitely on the right track :)

[minimi]

http://pastebin.com/ZxRAkLHd

I asked professor for help and he recommended using get methods.. I think the codes are written correctly at last and I was able to change String age to Integer age and it compiled.. but it returns null JOptionPane.. could anyone help me out what is wrong? I think while loop in the main method is written wrong....? Thank you!

[minimi]

public void bubbleSort() {
        String name = new String();
        Integer age = new Integer(0);
         boolean swap = false; // default swap
         
       //loop stops when swap not needed, list ordered
         while(!swap) {
            swap = true;
            for(PersonNode current = head; current.getNext() != null; current = current.getNext()){
               if(current.getAge() > current.getNext().getAge()){
                  name = current.getName();
                  age = current.getAge();
                 
                  current.setName(current.getNext().getName());
                  current.setAge(current.getNext().getAge());
 
                  current.getNext().setName(name);
                  current.getNext().setAge(age);                                              
 
                  swap = false;            
               }          
            }  
         }
      }
   } // end of LinkedList()

[apines]

Unless the array is sorted, the if statement on line 10 will be entered at least once, which will make swap=false , which means that the for loop will be executed only once. I recommend that you will take a look again at the bubble sort pseudo code, and then try to implement it with Java to work with linked lists.