• Post Reply Bookmark Topic Watch Topic
  • New Topic

Very frustrated noob: Insertsort on array, doubling array if it gets full  RSS feed

 
Larry Marks
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,
I have read through some of the posts on insert sort /arrays and see close but not exactly what I'm looking for. I don't want to use a library to do work for me, I want to do it myself and understand it.
I would like to see if anyone here can spare a few minutes looking and telling me:
1) Where my flaws are in the program.
2) what other flaws they see in my writing.
3) how they attack a problem, do they start with paper/pen ? Do they start with big items and work smaller or just start working it out on the keyboard?

Is there a written guide to a certain way of attacking a problem?


I have been working for hours trying to figure out these last few errors. Perhaps someone on these forums will help a little and not laugh too much. I have been in Java for a few weeks, and this is my first look at arrays.
I may have caused some damage by deleting stuff and starting over 3 or 4 times. ~I've spent maybe 20 hours trying to get this done. I know it is probably all of 30 min work for someone else, if that. Originally I tried writing a moving front end and back end, but that became way to complicated and I took out almost all of that code.

also: Do you normally attach code? or only paste it?
Thank you!
Larry

Note: When pasting in here, I deleted the print lines I used to see what was going on with. The only ones left are what I am trying to work into an error. That isn't important though, I can always delete that.

OrderedArrayList.java





Second File for testing.


OrderedArrayListTests.java

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One of the best ways to improve a program is to refactor complicated logic into Composed Methods. This example does some of what you want to do. Notice how clean and understandable the refactored version of the code is.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your insertion sort code seems way more complicated than it needs to be. You can find pseudocode of the algorithm on the Internet and it's much shorter than what you've come up with.




 
Larry Marks
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for the answer. I'll take a look at that web page some more. I've only looked a little at it and I don't understand it yet. I don't know much of the vocabulary yet.
One part of the program I have trouble with is compareTo.
I need to compare what I am inserting to each of the values down the line, but if any are null it messes things up. I assume compareTo cannot compare something to null, correct? So I keep adding if statements to only look at non-null elements. is there a better way to do this? (While still being simple). I wish i knew how to debug in eclipse but my instructor says that isn't part of the course. I'm trying to learn from youtube, ill spend a few more hours on it tomorrow but I can't neglect other work.

Thanks for your help.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
… and welcome to the Ranch
 
Andrew Kenyon
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Larry Marks wrote:

3) how they attack a problem, do they start with paper/pen ? Do they start with big items and work smaller or just start working it out on the keyboard?



Personally, I make sure I understand the problem as best as I can before trying to implement a solution. In this case, that may mean sitting down with
a pen and paper, writing a "random" sequence of 5 - 10 integers, and then stepping through the pseudo-code of the insertion sort algo. At each iteration
you'll mark exactly where the loop pointers are pointing, note when you've found the correct insert location for the integer (and how you knew that), then
manually shift however many integers are required to their new location, etc...

Then, I would implement the algorithm in the absolute simplest code possible (i.e. forget about generics, implementing Comparable, writing test code
before you even understand how the code is supposed to execute properly, dynamically resizing arrays, input validation, etc...). If the bare bones
implementation works as you expected it to (based on your whiteboard/notebook practice stepping through the algo), THEN comment it very well so
that Future Larry will still love you (Present Larry) when he has to read it again at some point.

Now, if you need to implement additional bells and whistles then introduce them one at a time, making sure you completely understand (and test) them
as you go along. That way if it doesn't work, you know exactly which changes are causing the issue. Trying to implement two (or more) features into your code
before you understand what you are doing is just asking for frustration. Tomorrow-morning-Larry (the one who got some sleep tonight because he sensibly implemented
one new feature at a time) will be very appreciative of you for sticking to this process.

And, now I've got about 15 minutes to get to class, so I'll sign off here.

Good luck!
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is a test to help you fix your bug:
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, some initial comments from reviewing your code:
Here are some things I think you can improve on

#1: Scope of variables
You have a bunch of effectively "global" variables at the top of your class. Variables should be declared to the minimum scope possible. The main one I have an issue with is the array counter "j". Best practice with arrays is to declare the array counter as part of the loop:
i.e. for (int j=0; j<array.length; j++)
Why do you have two arrays declared here? The only place I can see arrayB used is when you are copying values from one array to another after 'growing'.

#2: Write a toString method so you can easily examine the contents of your array for debugging (Ok, I see something similar there commented out)

#3: Some of your tests are testing multiple things. Best practice is to have each unit test test one process/thing. Tests that tests too much are hard to debug. For instance your testCounting method is also testing removing from the list.

Oh, and here are a couple more tests for ya.

 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!