Need help with looping/recursive algorithm in a method in Java

[PiPBoyV3]

Ok, I need help again. I was on here earlier today with a simple, yet hard to find problem regarding my code. Fortunately, I fixed it and improved my code more and more. I feel as though I am close to the final draft, but there is only one error stopping me now, and it is that my program is using more than 64 MBs (which I believe is the minimum) of heap space in the java virtual machine when I run my program. I can see why, as I'm basically trying to mergeSort, shellSort, and quickSort the same int array of data at the same time. I know every variable you add takes up a very small amount of memory (1 byte?); same goes for methods, loops, recursion, etc, but I'm still quite new to this so I don't know exactly how to make my code more efficient.

Anyway, the problem is I have these three sort methods running at the same time, and they are hogging too much memory. The first thing I thought of doing was splitting each into their own method, then calling them separately, but it achieved the same result. There's a way to do this, I know it (besides manually increasing the virtual machine's heapsize), but this is my first encounter with memory management in any programming language, so I'm at a loss. I'm also very tired. Regardless, here is my code, I would greatly appreciate it if someone could tell me what to do:

[url]http://pastebin.com/m6d7d094[/url]
[url]http://pastebin.com/m5ab1442c[/url]

I'm off to bed. Hopefully when I get up 7 hours from now someone will give me some advice so I can complete this fucking thing and move on with my life. I've literally been in my computer chair for hours at a time, for 2-3 days now, just trying to get this thing to work. Anyway, enough ranting. Thanks in advance.

[gforce7]

Well one thing i noticed is that you used ma.toLowerCase(). Since strings are immutable, that wont work. what you need to do is car.setMake(ma.toLowerCase()).

also, when checking if a string is empty, you should check the length, or at least I was taught that way, so:

while (ma.length() > 0)

[Wyzard]

[QUOTE=gforce7;18346100]Well one thing i noticed is that you used ma.toLowerCase(). Since strings are immutable, that wont work. what you need to do is car.setMake(ma.toLowerCase()).[/QUOTE]
If I wanted to lowercase the line immediately after reading it, before storing it into the car, I'd do

String ma = in.nextLine().toLowerCase();

However, I [i]think[/i] the intention in this case is just to do a case-insensitive comparison against the word "sort", which could be done like this:

if (ma.toLowerCase().equals("sort"))

but is simpler to do like this:

if (ma.equalsIgnoreCase("sort"))

[QUOTE=gforce7;18346100]also, when checking if a string is empty, you should check the length, or at least I was taught that way, so:

while (ma.length() > 0)[/QUOTE]
He did check the length, he just compared against "0" also for some reason. That seems pointless -- I see no reason to prevent the user from typing "0" as a response when things like "00" and "1" are accepted.

Unless you need your code to be compatible with older versions of Java, you can simply do

while (ma.isEmpty())

[editline]08:57AM[/editline]

The reason your program is running out of heap space and crashing is because you have an infinite loop in the getTempArray() method. Here's what leads up to the problem:

The setTempArray() method does nothing. Its loop never runs because you used '>' instead of '<' and the size of a list is never less than zero. Therefore nothing ever gets stored into the tmp and tmp2 lists.

Later, in getTempArray(), this loop also does nothing:

for (int i = 0; i < tmp.size(); i++)
    tmpvin = tmp.get(i);

because tmp.size() is always zero, since setTempArray() didn't put anything into it. Therefore tmpvin doesn't get set, so it's left holding the VIN of the last car entered (left over from the last call to setTempArray()).

The main loop in getTempArray() loops over all the cars and compares each one's VIN against the VIN of the last car (since that's what's in tmpvin). When they match (which happens when it gets to the last car, if not sooner), it adds that car to the end of tmparray... but assuming there's more than one car, tmparray was set to array during a previous run through this loop, so you're actually adding a new item to the end of the main array.

The result is that this loop in getTempArray() never reaches the end of the list because it keeps adding new items to it, making it grow bigger and bigger until your program runs out of memory.

It's not clear to me what these two methods are [i]supposed[/i] to do. I see that you're using the tmp array in your shellSort() method, but that looks fishy to me -- a sort procedure shouldn't be relying on the contents of some other list than the one it's supposed to be sorting. I'd delete these two methods and the associated "temp" variables (which shouldn't be instance variables anyway).

[PiPBoyV3]

Thanks for taking the time to write that out. The way the program initially worked was tmp and tmp 2 were a normal int array and a Comparable int array, each used by a different sort method. Well, when I tried to place elements into each while running gatherInfo(), nothing would ever get set because the array ArrayList always had a higher size than both of those. After being told everything would work better as ArrayLists, I switched everything to ArrayList calls, including the previous Comparable [] that each sort method took in, and now I agree that both are obsolete.

The setTempArray() and getTempArray() methods were a conglomeration of a snippet of code I got off of the internet to take the vin number from the car in ArrayList array, and set it to another int array for easier sorting by the methods, then put it back into place after sorting, since array is of <Car> type and contains two strings along with the vin number. But yes, I hardly paid attention to what was going on there, I assumed it worked. It's all a mess now. Would the correct way to do it just to sort array(i+2), so as to skip over every two strings, and only look at the VIN? Or set each vin to a seperate array entirely, then sort it and print...see the hard part is keeping the vin attached to the data it was input with. It would be terrific if you could walk me through this, this has all been a learning experience for me since I'm so new. My xfire name is: silverson, add me.

Anyway, my new code revision:

[url]http://pastebin.com/m68c5655e[/url] - CarSort
[url]http://pastebin.com/m750169d1[/url] - Car

I'm missing the link between tmp and array ArrayLists, so my sorting methods aren't running correctly, if at all. Run the program, enter a few snippets of data, then try sorting to get the error.

Help needed, PLEASE!

[Wyzard]

Well, printShell() causes an IndexOutOfBoundsException while printing the results since it uses <= rather than < to compare i against array.size(). Several other methods have the same mistake (matchTemp(), printMerge(), and printQuick()) so I assume it's not just a typo. Remember that because array indexes start at 0, the last valid array index is one [i]less[/i] than the array's size.

Anyway, the real problem, as you mentioned, is that you're sorting a list of integers, but it has nothing to do with the list of cars that you're supposed to be sorting. Solution is: don't do that. :-) Get rid of tmp, and just pass the list of cars into shellSort() and the other sorting methods. In the sort code, you can call getVin() where appropriate to get the integers that you need to sort with. (For example, tmp.get(i) would become something like cars.get(i).getVin().)

However, aside from the difference between cars and integers, your shellSort() implementation is broken because of the way you're "moving" items into position:

a.set(j, a.get(j-gap));

Suppose that the list is [1, 4, 3, 2], gap is 2, and j is 3. You've just compared items 1 and 3 (values 4 and 2) and found that they're in the wrong order. This line will overwrite index 3 with the value 4, turning this list into [1, 4, 3, 4]. The 2 has been lost. You need to shift the in-between elements (in this case, the 3 and the 2) downward to make room for the element being inserted at the end, so that the list becomes [1, 3, 2, 4] instead.

I'd also like to point out that you're using two different list variables in your shellSort(), one called "tmp" and one called "a". They happen to be the same list, because when you calll shellSort() in printShell() you pass tmp as the parameter, but referring to tmp directly in shellSort() is bad practice because it means that the method is tied to that specific list, and won't work properly if it's ever asked to sort any other list. (Personally, I'd make the shellSort(), quickSort(), and mergeSort() methods static, because these sorting algorithms are completely self-contained and should never need to refer to any variables other than their parameters.)