Lampsort: Leslie Lamport's Non-recursive Quicksort

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by taeric on Sunday December 07, 2014 @03:48PM (#8713513)

Threaded trees was what I had in mind.[1] I believe the example there still talks of checking a visited list, though. Either a misunderstanding on my part, or on that page. I'll have to check on my books. Later, sadly. :)

[1] http://en.wikipedia.org/wiki/Threaded_binary_tree

Edit: Apologies for a quick edit. I remembered I had a short implementation on my computer. Basically, when you follow a link, you know if it was a regular link or a thread. If it was a regular link, you could still go left from the new node. Otherwise, you visit and go right. Again, keep note of whether it was a thread or not. Repeat until done. (Make sense?)

[ Parent | on HN ]

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by al2o3cr on Sunday December 07, 2014 @06:59PM (#8714182)

"Again, keep note of whether it was a thread or not."

This sounds like the visited list again...

[ Parent | on HN ]

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by taeric on Sunday December 07, 2014 @07:20PM (#8714258)

You only have to remember the link you just followed. Basically, make a boolean "followedThread" and initialize to false. Then, go to the root and follow this algorithm

    if (!followedThread && left != null) 
        set followedThread <- curNode.left.isThread
        set curNode <- curNode.left.node
    else
        set followedThread <- curNode.right.isThread
        set curNode <- curNode.right.node

Only node you really have to special case is the root node, and you can do that by making its right.node == null. Then you just do this while curNode != null.

That make sense? (Also... very possible that I made a mistake here...)

[ Parent | on HN ]

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by hyt7u on Sunday December 07, 2014 @05:34PM (#8713866)

Ah, great, thanks. I wasn't thinking about modifications to the tree.

[ Parent | on HN ]

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by taeric on Sunday December 07, 2014 @05:53PM (#8713935)

Yeah, apologies if it looks like I was intentionally misleading. Was not my intent.

[ Parent | on HN ]