On 7/14/2015 1:15 AM, Paul Rubin wrote:
def quicksort(array, start, end):
midp = partition(array, start, end)
if midp <= (start+end)//2:
quicksort(array, start, midp)
quicksort(array, midp+1, end)
else:
quicksort(array, midp+1, end)
quicksort(array, start, midp)
I assume you know how quicksort and its partition step work. The idea
is you partition the array around the pivot element (midp is the index
of that element), then recursively sort the two partitions, doing the
smaller partition as a recursive call and the larger one as a tail call,
so that you use O(log n) stack depth instead of potentially O(n).
Thank you for the example. It I have ever seen how to minimize the max
stack needed for first calls, I have forgotten. First some comment:
1. There is no terminal condition, so the above will loop forever. The
body should start with 'if not terminal(start, end):' where terminal is
the actual expression. I did not write it because it depends on whether
'end' is the highest index or one past it.
2. There are no tail calls (call followed by return), so a tail-call
optimizer will not optimize this. A recur() function might be able to.
3. Mutation is anathema to functional programming, so a functional
programmer would never write and version of this, at least not without
holding his nose.
The tail-like calls in each branch can be avoided with assignment and
gobacks. In Python, we go-back with while loops. (IE, 'while' = 'label'
+ 'if' + 'goto'.) With minimal change to the above, we get (untested)
def quicksort(array, start, end):
while not terminal(start, end):
midp = partition(array, start, end)
if midp <= (start+end) // 2:
quicksort(array, start, midp)
start = midp+1
else:
quicksort(array, midp+1, end)
end = midp
I can understand that someone might prefer to break the symmetry of the
paired calls by wrapping the second with recur() (assuming that such a
function is sensibly feasible on *all* implementations). In the other
hand, I prefer the reduced-noise explicit assignment that highlights the
one parameter that gets rebound.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
