• Post Reply Bookmark Topic Watch Topic
  • New Topic

Stuck using quickSort to sort an ArrayList  RSS feed

 
Hans Hovan
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm writing a program that is supposed to sort objects (people, companies, etc.) based on criteria like last name, then first name, then ID number, and so on. The objects being sorted implement compareTo in their classes. I set up my sort class using the quickSort method (well, I tried to) and can't figure out what is wrong with it. It is strange, because if I add two objects and try to sort them it works OK but if I add three or more something goes wrong...the program will just hang there with no error message (maybe an infinite recursion?) Any suggestions or pointing out of obvious flaws would be appreciated.



For reference, the objects being sorted to have compareTo methods similar to this:



Again, thanks for any help.
 
Chan Ag
Rancher
Posts: 1090
14
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hans Hovan wrote:I'm writing a program that is supposed to sort objects (people, companies, etc.) based on criteria like last name, then first name, then ID number, and so on.


I would consider making it a generic method in that case. I would also consider passing a Comparator to the method ( I like comparators cause I like to handle nulls in them and then I'm sure how the comparison caters to null values ).

Hans Hovan wrote:


So that looks like an in place quick sort. But looks like there are few mistakes in there. Try writing the values in a piece of paper. Are those the values you were expecting? Isn't i supposed to move forward and isn't j supposed to move backwards? Let us consider an ArrayList of Integers containing 5 elements.
from is 0 and hence your pivot is the 0th element. i = -1 as per your logic. Is that what you intended? j is 5, i.e index for the 6th element if you had one. Is that what you wanted it to be?

Ok let's ignore this bit. Let's go further down.
Since -1 is less than 5, we enter the while loop.
i is now 0 again after the post increment. So now in the second while loop you are comparing the 0th element with the pivot element. But isn't pivot also the 0th element? So that comparison always returns false. Is this what the code should do at this point?
j is now 4, after the post decrement. So you keep decrementing j( your program has an i there, but I'm sure that is a typing error. yeah? ) till you get an element less than or equal to the pivot.
Once you find the element that is less than or equal to pivot, you swap it with the ith element, which is where your pivot is.
Is that what you intended?

About the following--


I have not really given much thought to this but is it possible that this loop could continue even though i became > j cause that check is the outer check only.

How about you run that code on a piece of paper, assigning values to variables as you process it. Do you see the mistakes?

I don't like those casts. See if it's possible to have something which is safer and does not require those casts?

HIH,
Chan.

 
Chan Ag
Rancher
Posts: 1090
14
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hans Hovan wrote:




I would also consider adding a return statement, as the first instruction of the sort method, to cater to the case of having fewer than 2 elements in the ArrayList.

Chan.
 
Hans Hovan
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you very much for the help.

That gave me some new ways to think about it.

It turned out to get it working the way I wanted it all I had to do was fix my typing error in the second (elements.get(i))), which should have been a j. But your suggestions helped make my code more robust and I have a better understanding of what is going on. Again, Thank you!
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!