3 ms·
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead. Please tell me what imperative quicksort
by kccqzy 7y ago
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead.
Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space.
Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.
- foota 7y agoI don't know that I would ever do this, since O(lgn) space is normally trivial, but couldn't you use a RNG that's based on like the depth and start position of a given "stack frame" of a recursion-less quicksort? Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple? And run that in reverse for going back up the stack. edit: Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space. https://link.springer.com/chapter/10.1007/BFb0016252 https://link.springer.com/chapter/10.1007/BFb0016252 The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.
- ivalm 7y agoFor non recursive quicksorts see code at bottom of this link: https://www.geeksforgeeks.org/iterative-quick-sort/ https://www.geeksforgeeks.org/iterative-quick-sort/
- kccqzy 7y agoThat link basically just simulates recursion by defining a stack in the function. It recognizes that in the recursive version among the stack variables only the two indexes need to be stored so it stores them. It is even less space efficient than the recursive version because it always allocates O(n) space.
- scythe 7y agoThe path towards O(1) space instead of O(log n) space is fraught with technicalities. At the bottom, you realize that no matter what algorithm you use, you always store the array size in lg(n) bits! So it makes more sense to say “less memory” rather than O(1) memory for sorts.