• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

More Array sorting trouble

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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):
 
Ranch Hand
Posts: 142
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Try good old array.sort?
 
Miklos Szeles
Ranch Hand
Posts: 142
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 142
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Victor: I think it's an exercise to implement it himself, and not use any ready to use solution.
 
Leonard Brandeis
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 142
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Ranch Hand
Posts: 492
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 177
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
reply
    Bookmark Topic Watch Topic
  • New Topic