I have both versions of QSort -- recursive and iterative.
I didn't have to make any significant changes to the recursive version, except adding a stack.
Thus, both versions are equivalent in their functionality. i.e. they do the same thing.
Also, I've noted that there are certain differences between recursive and iterative versions.
For example, qsort sorts on on an array on indices from i to j, where i<j.
If you happened to generate i and j such that i>=j (no need to sort), recursive version had to actually enter a function to see this, and return right away.
With iterative version you first generate i and j, and then push them on the stack. If you generate i>=j, you have an option to not push them on the stack, thus "saving" a would-be recursive call. In other words, in iterative version you can "move" certain things out of the recursive function, outside the recursive function, if this makes sense. |
