1
\$\begingroup\$

I have been searching for ways to make my algorithm more efficient but most answers told me to divide the array into two differente arrays one of less elements and one of greater elements and then merge it, but that would make the QuickSort a non in-place sort anymore.

So, if someone could tell me a way of improving the efficiency of my code and if it is well designed or not, without affecting the in-place characteristic of the algorithm.

def QuickSort(array, right, left):
    left_original = left
    right_original = right
    pivot_pos = right
    while True:
        for right in reversed(range(pivot_pos, right+1)):
            if (array[right] < array[pivot_pos]):
                break
        for left in range(left, pivot_pos+1):
            if (array[left] > array[pivot_pos]):
                break
        if right == left:
            break
        if array[pivot_pos] == array[right]:
            pivot_pos = left
        elif array[pivot_pos] == array[left]:
            pivot_pos = right
        array[right], array[left] = array[left], array[right]
        right = right_original
        left = left_original
    right1 = pivot_pos - 1
    left1 = left_original
    right2 = right_original
    left2 = pivot_pos + 1
    if (right1 > left1):
        QuickSort(array, right1, left1)
    if (right2 > left2):
        QuickSort(array, right2, left2)


\$\endgroup\$
1
  • 2
    \$\begingroup\$ Hopefully this is just for learning, because the built-in sort should nearly always be preferred to hand-rolled code. \$\endgroup\$
    – Reinderien
    Jan 4 at 22:12
1
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.