• 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

Partition in quicksort

 
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15484
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 79151
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15484
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
But it still calls the method with return??
 
Stephan van Hulst
Saloon Keeper
Posts: 15484
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15484
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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:

 
reply
    Bookmark Topic Watch Topic
  • New Topic