Python QuickSort returning original input

Question

So here is my quicksort code

def quicksort(A):
    if len(A) > 1:
        pivot = A[0]
        L = []
        E = []
        R = []
        for i in A:
            if i < pivot:
                L.append(i)
            elif i == pivot:
                E.append(i)
            else:
                R.append(i)
        quicksort(L)
        quicksort(R)
        A = L + E + R

And the output when I run

array = [5,6,3,2,7]
print "original array" + str(array)
quicksort(array)
print "sorted array" + str(array)

Is

original array[5, 6, 3, 2, 7]
sorted array[5, 6, 3, 2, 7]

However, when I step through the function with the debugger, the last value A ever holds is [2,3,5,6,7] which is sorted, why does A not hold this after the function is executed?

the A is not a pointer from array ; in function you change A , and array no changed ! — Baba
– Baba, Commented Jan 19, 2014 at 21:52

Martijn Pieters · Accepted Answer · 2014-01-19 21:44:17Z

5

You build a new list A = L + E + R, rebinding the local name. The original list is unaffected.

You need to return the new list objects:

def quicksort(A):
    if len(A) > 1:
        pivot = A[0]
        L = []
        E = []
        R = []
        for i in A:
            if i < pivot:
                L.append(i)
            elif i == pivot:
                E.append(i)
            else:
                R.append(i)
        L = quicksort(L)
        R = quicksort(R)
        return L + E + R
    return A

This returns a new list object:

>>> quicksort([5,6,3,2,7])
[2, 3, 5, 6, 7]

Alternatively, update the list in-place by using slice assignment:

def quicksort(A):
    if len(A) > 1:
        pivot = A[0]
        L = []
        E = []
        R = []
        for i in A:
            if i < pivot:
                L.append(i)
            elif i == pivot:
                E.append(i)
            else:
                R.append(i)
        quicksort(L)
        quicksort(R)
        A[:] = L + E + R

Now the original list is altered in-place:

>>> lst = [5,6,3,2,7]
>>> quicksort(lst)
>>> lst
[2, 3, 5, 6, 7]

answered Jan 19, 2014 at 21:44

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

abarnert Over a year ago

He doesn't need to return them; he's trying to mutate the values in-place, and that's a perfectly reasonable and doable thing, he just didn't do it right.

Martijn Pieters Over a year ago

@abarnert: Hrm, I guess with creating new L and R objects that's feasible.

abarnert Over a year ago

It's not just feasible, he's almost got it right. See my answer—just change A = to A[:] = , and his code works exactly as desired.

Martijn Pieters Over a year ago

@abarnert: yeah, I was assuming that the recursive calls required to have lower and upper bounds passed along, before I saw that these calls are given a new list object.

Igglyboo Over a year ago

Thanks very much, I was originally doing it with return values but for a reason specific to my homework assignment it works better when I just mutate the list in place.

abarnert · Accepted Answer · 2014-01-19 21:44:10Z

The problem is that the last line doesn't do what you seem to think it does:

A = L + E + R

This adds L, E, and R together into a new list, and binds that new list to the local variable A. It doesn't affect the list that A used to be bound to in any way.

What you probably wanted to do was replace the contents of the existing list that A is bound to. Like this:

A[:] = L + E + R

You ask "why does A not hold this after the function is executed?" Well, after the function is executed, A doesn't exist at all. That's the whole point of a local variable.

Of course array exists. And array and A are originally references to the same list. If you mutate that list, you get what you want. If you make A refer to a different list, you don't.

Collectives™ on Stack Overflow

Python QuickSort returning original input

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related