• Post Reply Bookmark Topic Watch Topic
  • New Topic

Quicksort doesnt work in certain cases.  RSS feed

 
Bob Ivanovich
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As I was testing my quicksort I noticed a problem. Sometimes it arranges the array in alphabetical order and sometimes it does not. A more clear is example it like if I have "p, o, j, l" as my array it sorts it to "j, o, l, p" which is wrong. "l" should be before "o" However if I add "a" to the array it sorts to "a, j, l, o, p" which is correct. Why is this happening?

My code:

 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Bob,

While posting questions on algorithms, it is always helpful to also post the pseudo-code or your program logic in text so people can easily help you if they see a logic error.

It might also be better to actually dry run it yourself, assigning values to variables in a piece of paper like a computer would so you would know how your computer would solve it. I just did that to solve your problem.

Now coming to your question, do you think your method partition should return the value of hi if lo is greater than or equal to hi? Shouldn't by this time hi become smaller than lo? If so, is that happening?

If that is not happening, you might want to check your code to see why it is not happening.

Hint : Look at those two while loops.








 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, I'm not really sure if my post helped you at all. So I think I'm going to try to make it a little better this time.

If I was coding that in place quick sort method, I would have changed those two while loops as follows.



This is because with every call of partition method, the splitpoint ( the hi you return in your partition method ) should find its right place in the array. That happens only after lo becomes greater than hi and not when lo == hi.

Hope this will help.
 
Bob Ivanovich
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you so much! It worked.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!