• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Quicksort doesnt work in certain cases.

 
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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:

 
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you so much! It worked.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic