5 ms·
Where Quicksort uses the recursion stack to maintain the `intervals` implicitly, Lampsort instead uses some set data structure to maintain this set of subproble
by rav 12y ago
Where Quicksort uses the recursion stack to maintain the `intervals` implicitly, Lampsort instead uses some set data structure to maintain this set of subproblems explicitly.
It reminds me of the way you turn recursive depth-first search (recurse on children that have not been visited) into non-recursive depth-first search (push the children that have not been visited onto the DFS stack). Calling it "non-recursive" is a bit misleading, since you're trading recursion stack space for an actual data stack to maintain the recursion you are supposed to avoid -- but it is a useful program transformation to know.
- taeric 12y agoThere are ways to do a DFS of a tree without any sort of stack, though. This sounds more like a nitpick on stack vs set. You still have a data structure that grows in lg(n).
- hyt7u 12y ago> There are ways to do a DFS of a tree without any sort of stack, though What do you mean by this? You need a way to say that the unexplored nodes we've most recently found are the ones we explore first. How do you do that (with constant time operations) without what's effectively a stack?
- taeric 12y agoThreaded 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 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?)
- hyt7u 12y agoAh, great, thanks. I wasn't thinking about modifications to the tree.
- taeric 12y agoYeah, apologies if it looks like I was intentionally misleading. Was not my intent.
- al2o3cr 12y ago"Again, keep note of whether it was a thread or not." This sounds like the visited list again...
- taeric 12y agoYou 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...)