Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lampsort: Leslie Lamport's Non-recursive Quicksort

bertrandmeyer.com

Post reply on HN
Print view View original

11–20 of 46 posts

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#11

Post by bkirwi »

jwmerrill wrote: post #3

> His trick is to ask the audience to give a non-recursive version of Quicksort, and of course everyone starts trying to remove the recursion, for example by making the stack explicit or looking for invertible functions in calls. But his point is that recursion is not at all fundamental in Quicksort. I'm not completely sure what distinction Meyer is trying to draw between the implementation he discusses, and "making…

Yes, that's the principal idea, I think -- separating out the implementation details from the actual conditions that are necessary for correctness. IIRC, I've seen another presentation of this where the author used that freedom to implement a work-stealing quicksort across multiple threads.

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#12

Post by Cushman »

jwmerrill wrote: post #3

> His trick is to ask the audience to give a non-recursive version of Quicksort, and of course everyone starts trying to remove the recursion, for example by making the stack explicit or looking for invertible functions in calls. But his point is that recursion is not at all fundamental in Quicksort. I'm not completely sure what distinction Meyer is trying to draw between the implementation he discusses, and "making…

Watching the source lecture[0], it's not about how the code is written so much as how the function is specified. It's easier to describe quicksort as a few set equations without invoking the concept of recursion, but since we don't write code like that people can't get to it easily.

The nuts-and-bolts difference is in fact that it's a set and not a stack, but the underlying question is, why do we all treat the set implementation as the derived version?

[0] http://channel9.msdn.com/Events/Build/2014/3-642 ~35m

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#14

Post by oggy »

> Formal specification languages look remarkably like programming > languages; to be usable for significant applications they must meet > the same challenges: defining a coherent type system...

Lamport disagreed with this statement before [1], wonder what he'd say nowadays (he's been known to change his mind). Gossip warning: Lamport gave a talk at Meyer's university a few years back, bashing OOP. Meyer's a huge OOP proponent.

[1]: http://research.microsoft.com/en-us/um/people/lamport/pubs/l...

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#16

Post by badubu »

Cushman wrote: post #12
jwmerrill wrote: post #3

> His trick is to ask the audience to give a non-recursive version of Quicksort, and of course everyone starts trying to remove the recursion, for example by making the stack explicit or looking for invertible functions in calls. But his point is that recursion is not at all fundamental in Quicksort. I'm not completely sure what distinction Meyer is trying to draw between the implementation he discusses, and "making…

Watching the source lecture[0], it's not about how the code is written so much as how the function is specified. It's easier to describe quicksort as a few set equations without invoking the concept of recursion, but since we don't write code like that people can't get to it easily. The nuts-and-bolts difference is in fact that it's a set and not a stack, but the underlying question is, why do we all treat the set im…

> but since we don't write code like that people can't get to it easily

which likely sums up what Lamport is trying to get across - express your work equationally, determine properties and generally understand what you're dealing with and then later, you can 'compile your equations' down to a particular implementation. from my own practice, i've found that it is much easier to reason about equations and reflect it down into code than to try and reason about the code

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#17

Post by yason »

I hiss at the term "non-recursive quicksort" which is used a lot. Quicksort per definition is recursive logically. The same computation recurs in the subarrays, you know.

Whether you maintain the state by using the programming language's own stack, a separate stack, a queue, or some other data structure either implicitly or explicitly is a matter of implementation. The amount of space you need to allocate for the program state as a function of the size of the input is the same regardless.

In a high level enough language it doesn't matter because you are to encode, in that language, your intent to apply the same process again and again to the subpartitions until everything is sorted, and a sufficiently smart compiler could choose any implementation that best suits the underlying hardware.

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#18

Post by tedunangst »

Cushman wrote: post #8

If I understand the argument, the use of a set rather than a stack encodes the observation that the order of execution of adjacent partition operations isn't important. That ordering is information you don't have to store, meaning you can choose any set-like data structure, and being able to choose your access is theoretically useful: For example, by following a rule like "partition the smallest interval first", you…

"Smallest interval first" is exactly what naive recursion gives you.

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#19

Post by mpweiher »

yason wrote: post #17

I hiss at the term "non-recursive quicksort" which is used a lot. Quicksort per definition is recursive logically. The same computation recurs in the subarrays, you know. Whether you maintain the state by using the programming language's own stack, a separate stack, a queue, or some other data structure either implicitly or explicitly is a matter of implementation. The amount of space you need to allocate for the pro…

"The same computation recurs"

Hmm...you mean like in a loop?

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#20

Post by truantbuick »

I'm not sure I agree with the idea that this somehow characterizes the idea of quicksort better.

Technically, you can always convert a recursive algorithm to iterative and back again (and not just with existence arguments -- it can be generally constructed), so why pick on quicksort specifically?

The only thing achieved here is putting the partitioning of the list and sorting in two separable parts. Whether that characterizes quicksort any better is a matter of opinion, I reckon.

Post reply on HN