This week's book giveaway is in the NodeJS forum.
We're giving away four copies of Serverless Applications with Node.js and have Slobodan Stojanovic & Aleksandar Simovic on-line!
See this thread for details.
Win a copy of Serverless Applications with Node.js this week in the NodeJS 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
  • Jeanne Boyarsky
  • paul wheaton
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Ron McLeod
  • Tim Moores
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Vijitha Kumara

Partition in quicksort  RSS feed

 
Ranch Hand
Posts: 99
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Ranchers!

I am working on my old assignment and cannot remember why I wrote things the way I did (I hear you Junilu, this is my fault for not commenting !, and I agree).

This part of the code is written for a quicksort choosing a random pivot. But why does the partition_random returns the partition? Wouldn't it be easier for the partition_random to return an index (index of the new random pivot) and send it to quicksort?
I tried of course and I get a wrong assertion.

Can someone please help me to cast a light on that?

 
Saloon Keeper
Posts: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Wouldn't it be easier for the partition_random to return an index (index of the new random pivot) and send it to quicksort?


This is exactly what is currently happening.

D.J. Quavern wrote:I hear you Junilu, this is my fault for not commenting


Nope. It's your fault for not writing clear code. A well written program mostly documents method contracts, and doesn't need a lot of comments in method bodies.

A comment like "j will run from low to one less than the last element" is really really useless. You're essentially writing the code twice, once in Java and once in English. Instead of writing comments like that, document your methods like so:

With documentation like this, you can easily see that the return value is not a partition, but the index of the split point. This index is then returned to the partition_random() method (which should have been called partitionUsingRandomPivot()), which in turn returns it to the quicksort() method. The quicksort() method uses this index to sort the two partitions recursively.
 
Marshal
Posts: 63849
209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:. . . A comment like "j will run from low to one less than the last element" is really really useless.  . . . .

And rather inaccurate, too; you are probaby not running up to one less than the last element. By the way: it might be better to call that the penultimate element
 
D.J. Quavern
Ranch Hand
Posts: 99
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, very much m'y faut indeed.

I still don't get why the partition_random returns a method if it should return a split index?
 
Campbell Ritchie
Marshal
Posts: 63849
209
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please don't say anything returns a method; that doesn't occur in Java®.
 
Stephan van Hulst
Saloon Keeper
Posts: 9997
208
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Like Campbell says, you can't return a method. You call the method and return its return value.
 
D.J. Quavern
Ranch Hand
Posts: 99
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But it still calls the method with return??
 
Stephan van Hulst
Saloon Keeper
Posts: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, it calls the partition() method. The partition() method returns an index. Then that index is also directly returned by partition_random(). Is it easier to understand if we first assign it to a variable?

Anything in particular you don't understand?
 
D.J. Quavern
Ranch Hand
Posts: 99
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes. It is easier to see. But i wonder if it can't be made in a more straightforward way?
 
Stephan van Hulst
Saloon Keeper
Posts: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What do you mean by more straightforward? What about returning the result of the call directly is not straightforward to you?
 
Sheriff
Posts: 13392
221
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

D.J. Quavern wrote:Yes. It is easier to see. But i wonder if it can't be made in a more straightforward way?


The way it was before was pretty much as straightforward as you could get. I would refactor a little bit to separate the random pivot point calculation:

 
The overall mission is to change the world. When you've done that, then you can read this tiny ad:
global solutions you can do at home or in your backyard
https://www.kickstarter.com/projects/paulwheaton/better-world-boo
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!