This week's book giveaway is in the Go forum.
We're giving away four copies of Head First Go and have Jay McGavren on-line!
See this thread for details.
Win a copy of Head First Go this week in the Go forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Devaka Cooray
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Tim Holloway
  • Claude Moore
  • Stephan van Hulst
Bartenders:
  • Winston Gutkowski
  • Carey Brown
  • Frits Walraven

Bug in school assignment, again  RSS feed

 
Ranch Hand
Posts: 81
Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi dear Ranchers,
I am still working on my quicksort for school. I tried to implement Yaroslavskiy's quicksort (double pivot with recursion but my program does not sort arrays longer than 100).



I tried to follow step by step this tutorial https://www.youtube.com/watch?v=yRJ1Zb4pCM4  and understand what was going on. My eyes are literally bleeding right now so I appreciate greatly any help to understand where it went wrong.

Shall I give up and implement another double pivot with iteration instead?
 
Sheriff
Posts: 5750
149
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Deja Quavern wrote:Hi dear Ranchers,
I am still working on my quicksort for school. I tried to implement Yaroslavskiy's quicksort (double pivot with recursion but my program does not sort arrays longer than 100).


What happens with an array bigger that 100 elements?
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It does not sort it. Sometimes the mistake is at element[0], sometimes later.
 
Knute Snortum
Sheriff
Posts: 5750
149
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I bet it's when the actual QuickSort is used and not Insertion sort.

One thing that bugs me -- and this may be your problem -- is that quicksort() is static.  There's no reason for it to be, and it may be stopping the recurrson.  I'm not sure, but it's a quick change.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wonder why it does sort small arrays for 10/12 numbers though....
 
Saloon Keeper
Posts: 9869
199
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Because it's not using your quicksort algorithm, but an insertion sort.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Because it's not using your quicksort algorithm, but an insertion sort.




Ooooo no. The quicksort does not work.. AT ALL!
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Knute Snortum wrote:I bet it's when the actual QuickSort is used and not Insertion sort.

One thing that bugs me -- and this may be your problem -- is that quicksort() is static.  There's no reason for it to be, and it may be stopping the recurrson.  I'm not sure, but it's a quick change.



You are my heroic hero. It does go longer than usual!

Can you kindly explain why static makes a difference?

But it still crashes at some point (I have 50 tests, it crashes at test 15).
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you forgot to make sure that pivotOne is less than pivotTwo.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you mean to add a condition here as well, in addition to the one that checks if high is bigger than low?
_20190310_163441.JPG
[Thumbnail for _20190310_163441.JPG]
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No. Those are just starting and ending indices of the portion of the array to sort. What I mean is that Yaroslavskiy's algorithm prescribes that the value of the first pivot must be less than the value of the second pivot. So you basically need to do the following:
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:No. Those are just starting and ending indices of the portion of the array to sort. What I mean is that Yaroslavskiy's algorithm prescribes that the value of the first pivot must be less than the value of the second pivot. So you basically need to do the following:



Thank you SO much!

I really was unable to figure it out myself and I am slightly ashamed. Now it is working as it should.

Can you please tell me why the static was a problem?
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It wasn't, and I would have made the method static as well, because it's not using instance fields.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:It wasn't, and I would have made the method static as well, because it's not using instance fields.



Can I give you a cow, or nominate you for a cow ?
I was really unable to figure out the issue before you pointed out the pivotOne and pivotTwo dynamics!
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome.
Staff note (Liutauras Vilda):

On behalf of OP

 
Something about .... going for a swim. With this tiny ad ...
Become a Java guru with IntelliJ IDEA
https://www.jetbrains.com/idea/
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!