Forums Register Login

Stuck using quickSort to sort an ArrayList

+Pie Number of slices to send: Send
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.
1
+Pie Number of slices to send: Send
 

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.

1
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
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!
It would give a normal human mental abilities to rival mine. To think it is just a tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 7623 times.
Similar Threads
QuickSort Question
My Quicksort - Your Opinion on programming style
Comparing values
error: class, interface, or enum expected
recursive quick sort issues
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 11:25:27.