This week's book giveaway is in the Cloud/Virtualization forum.
We're giving away four copies of Grokking Bitcoin and have Kalle Rosenbaum on-line!
See this thread for details.
Win a copy of Grokking Bitcoin this week in the Cloud/Virtualization 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
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Paul Clapham
  • Devaka Cooray
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Frits Walraven
Bartenders:
  • Carey Brown
  • salvin francis
  • Claude Moore

Bug in school assignment, again  RSS feed

 
Ranch Hand
Posts: 99
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: 5924
155
Chrome Eclipse IDE Java Postgres Database Ubuntu 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: 99
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: 5924
155
Chrome Eclipse IDE Java Postgres Database Ubuntu 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: 99
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: 10107
212
  • 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: 99
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: 99
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: 10107
212
  • 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: 99
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: 10107
212
  • 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: 99
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: 10107
212
  • 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: 99
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: 10107
212
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome.
Staff note (Liutauras Vilda):

On behalf of OP

 
Can you really tell me that we aren't dealing with suspicious baked goods? And then there is this tiny ad:
Create Edit Print & Convert PDF Using Free API with Java
https://coderanch.com/wiki/703735/Create-Convert-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!