Fix your function signature. Most Python programmers use lowercase for function
names. Even more important, don't swap the order the left and right:
# No: why is "left" to the right of "right"?!?
def QuickSort(array, right, left):
...
# Yes: less chance for confusion.
def quicksort(array, left, right):
...
Don't make the caller know your implementation details. Forcing the caller
to pass values for left and right is not convenient for your users; it is
somewhat error prone (for example, in some cases you can pass the wrong
indexes, the function will complete without error, but the list won't be
sorted); and it's not needed because Python makes it easy to define a function
with optional arguments:
def quicksort(xs, left = 0, right = None):
if right is None:
right = len(xs) - 1
...
Ranges have a step value. If you are using range(), you don't need
reversed(). Use a negative step:
for right in range(right, pivot_pos - 1, -1):
...
What about empty sequences?. Currently your code raises an error. This
problem is related to the next point.
Enforce recursive termination in one spot, almost always at the beginning.
As a general rule for recursive functions, enforce the termination condition at
the outset -- and only there. Your code makes a very common mistake of trying to
look into the future: before making the recursive call, you check for
preconditions. I observed this mistake in many software engineering
interviews, and it almost always caused the applicants to become more
confused. The better approach is to be confident: just make the recursive call
and let the function handle its own preconditions. Here's that point
illustrated with a code comparison:
# If we try to look into the future, additional variables
# are spawned, increasing complexity.
def quicksort(array, left, right):
...
right1 = pivot_pos - 1
left1 = left_original
right2 = right_original
left2 = pivot_pos + 1
if (right1 > left1):
quicksort(array, left1, right1)
if (right2 > left2):
quicksort(array, left2, right2)
# Things are simpler if we blindly recurse, letting the function
# enforce preconditions in a natural manner.
def quicksort(array, left, right):
if right <= left:
return
...
quicksort(array, left_original, pivot_pos - 1)
quicksort(array, pivot_pos + 1, right_original)
Using top-down implementation: an alternative to consider. Although your
current implementation appears to work correctly, I found it difficult to
reason about. For example, it seems like the main while-true loop might be
doing repetitive work, because on every iteration right and left are reset
to the original boundaries -- but perhaps I overlooked a detail. Either way,
the core idea of quicksort is very intuitive: we select a pivot value and make
the necessary swaps to enforce the quicksort invariant, namely small values < pivot value <= large values. But the implementation does not build on that
intuition or make it evident, either in code or in comments to guide the
reader. The implementation is additionally complex because several variables
are changing at once: right is being pushed downward, left pushed upward,
pivot_pos is sometimes altered based on those changes, then we swap a large
value and a small value, and then left and right are reset. I guess that
has a resemblance to quicksort (and is probably correct) but the alignment
between the code and the intuition not super obvious. Sometimes when struggling
to write an intuitive implementation (as distinct from a merely working one), I
will use a top-down approach. First we start with something clear and basic:
def quicksort(xs, i = 0, j = None):
# Set optional arguments.
if j is None:
j = len(xs) - 1
# Base case: do nothing if indexes have met or crossed.
if not i < j:
return
# Partition the sequence to enforce the quicksort invariant:
# "small values" < pivot value <= "large values". The function
# returns the index of the pivot value.
pi = partition(xs, i, j)
# Sort left side and right side.
quicksort(xs, i, pi - 1)
quicksort(xs, pi + 1, j)
Implement the functions that your top-level design omitted. So far, we
have simplicity and clarity, but only because we've deferred the trickiest
part: how to do the partitioning. But the top-down approach has a big benefit
in that we've reduced the size the problem considerably: instead of doing
sorting, we are merely partitioning; instead of build a user-facing function, we
are writing a utility function intended for use only by our quicksorter; and
instead of building a recursive function, we are building a regular function.
In my notes from various algorithm classes, I have a quicksort partitioning
function along the following lines. Note how some of its simplicity comes from
the fact that we are not modifying too many values: k which is just the
primary iteration variable, and pb which represents the current
partitioning boundary. Also note how additional simplicity comes from writing
another utility: the swap() function. If we were writing a mission-critical
sort function and cared about raw speed, we would not use that approach;
instead, we would do the swapping in line. However, in this case we are
focusing on algorithmic clarity. In that context, moving the grubby swapping
details elsewhere is a benefit.
def partition(xs, i, j):
# Get the pivot value and initialize the partition boundary.
pval = xs[i]
pb = i + 1
# Examine all values other than the pivot, swapping to enforce the
# invariant. Every swap moves an observed "small" value to the left of the
# boundary. "Large" values are left alone since they are already to the
# right of the boundary.
for k in range(pb, j + 1):
if xs[k] < pval:
swap(xs, k, pb)
pb += 1
# Put pivot value between the two sides of the partition,
# and return that location.
swap(xs, i, pb - 1)
return pb - 1
def swap(xs, i, j):
xs[i], xs[j] = xs[j], xs[i]
