aspose file tools*
The moose likes Beginning Java and the fly likes More Array sorting trouble Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "More Array sorting trouble" Watch "More Array sorting trouble" New topic
Author

More Array sorting trouble

Leonard Brandeis
Greenhorn

Joined: Sep 25, 2009
Posts: 8
This seems similar to a question I posted last week (all of your help was greatly appreciated, by the way), and yet I can't quite figure it out. I have an array of integers again, which I'm initializing with no elements for reasons you'll soon see. I have a method, add() that, in addition to adding the new integer, keeps the array sorted. So long as I keep the array size limited to the number of elements I actually want in the array, it works fine. Hence my increaseSize() function only recreates the array to list.length + 1 instead of doubling it as my book suggests. If I don't do it this way, I run into trouble based on the fact that all of the ints are initialized to zero whether I want then to or not. I've played with many variations here using both a selection sort version and an insertion sort version. I'm also keeping a counter, numElements, so that I only print the number of intended elements, but if I allow the array to grow I still wind up with a whole list of zeros that I don't want. Can anyone point me in a better direction? Here's the code with both sorts (one commented out):
Miklos Szeles
Ranch Hand

Joined: Oct 21, 2008
Posts: 142
Hi Leonard,
You mentioned a problem but you posted another code which makes hard to help. Please post real and runnable code. And please also provide a test case which producing not wanted results.
The suggested solution doubles the size of array for performance reasons. You don't have to create a new array, and copy all the elements on every add.

If you use this code when you increase the list by doubling its size, then you will run into trouble here. What will happen when the list size is 2 with 2 elements, and you want to add a new element? Think about it, and then you will recognize the problem.
Leonard Brandeis
Greenhorn

Joined: Sep 25, 2009
Posts: 8
Here's a scaled down version I've been toying with to try and figure it out:


If I initialize the array to be the exact size I want, it works fine, but if I initialize the array to a larger size and only add five elements, I run into to trouble with zeros.

The same problem happens when I try a different sorting algorithm like this one:



As written(new int[5]), this sort works fine, but if the array is initialized to a larger size there are problems.
Victor Twomey
Greenhorn

Joined: Oct 19, 2008
Posts: 5
Try good old array.sort?
Miklos Szeles
Ranch Hand

Joined: Oct 21, 2008
Posts: 142
The problem is that you want to do something with the zeros. Why? You should simply ignore them. You have to keep a variable in which you store the number of elements(not the list size), and do every operation based on the element count not based on the list size.
Miklos Szeles
Ranch Hand

Joined: Oct 21, 2008
Posts: 142
Victor: I think it's an exercise to implement it himself, and not use any ready to use solution.
Leonard Brandeis
Greenhorn

Joined: Sep 25, 2009
Posts: 8
Yeah, I guess the point is so I'll understand how the sort function actually works. I've tried using a counter and just printing out the five elements I want instead of the whole array, but if the array is bigger than I want, I wind up with five zeros being printed - all of the numbers I want to sort get shifted to the right of the zeros.
Miklos Szeles
Ranch Hand

Joined: Oct 21, 2008
Posts: 142
The counter is not only about the printing, it's also about inserting and sorting. It's simple. Use a counter, whenever you insert a new element check if there's more space(enlarge if necessary) and then insert the new element to the counter position.
Example: You have 6 element(your array size is 8), a new element have to be inserted into the array at the 6.th position.
The new element count is 7. You sort only the first 7 element, you print only the first 7 element. This works.
Can you tell me what is not clear? Can you post the code of your trying so then we can point out the problem with it?
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

So what I'm getting from the discussion is that you want to print the sorted array without any of the zeros?

You can easily add a statement to your loop that prints the array out so that the zeros are not included.

Hopefully this helps,
Hunter

P.S. The best way to figure out how the sort algorithms work is solving them by hand.


"If the facts don't fit the theory, get new facts" --Albert Einstein
Max Rahder
Ranch Hand

Joined: Nov 06, 2000
Posts: 177
By the way, it's sometimes interesting and educational to read the Java source. Look for the Collections#sort() method and see what it calls...
http://www.docjar.com/html/api/java/util/Collections.java.html
http://www.docjar.com/html/api/java/util/Arrays.java.html
Leonard Brandeis
Greenhorn

Joined: Sep 25, 2009
Posts: 8
Thanks for all of the suggestions...They got me pointed in the right direction. After way too much time looking at it, and finally giving in and solving it by hand (thanks Hunter), I realized my counter was in the wrong place and thus wasn't counting what it was supposed to be counting.

This site is great! Thanks again everyone.
 
wood burning stoves
 
subject: More Array sorting trouble