My quick sort code gives me wrong result when printed second time

Question

I'm new to Python and this is the quick sort code I wrote:

def Quick(List):
    if len(List) <= 1:
        return List
    pivot = List[0]
    l_idx = 0
    r_idx = len(List) - 1
    
    while l_idx != r_idx:
        while List[l_idx] < pivot and l_idx < r_idx:
            l_idx += 1
        while List[r_idx] > pivot and l_idx < r_idx:
            r_idx -= 1
        if l_idx < r_idx:
            List[l_idx], List[r_idx] = List[r_idx], List[l_idx]    
    
    List = Quick(List[0: (l_idx)]) + [List[l_idx]] + Quick(List[(l_idx + 1):])
    return List

The list I'm trying to sort is [598, 862, 950, 953, 373, 981, 201, 258, 427, 669].

If I run the following code, I'll get

xxx = [598, 862, 950, 953, 373, 981, 201, 258, 427, 669]
print(xxx)
# Gives me: [598, 862, 950, 953, 373, 981, 201, 258, 427, 669]
print(Quick(xxx))
# Gives me:[201, 258, 373, 427, 598, 669, 862, 950, 953, 981], which is the correct result.
print(xxx)
# Gives me: [427, 258, 201, 373, 598, 981, 953, 950, 862, 669], which is not the correct result.

I'm wondering why I get a completely different result than the one I returned when I print the list "xxx" the second time. Thanks!!

Do you want the second `print(xxx)` to print your sorted list, or the original unsorted list? — Jethro Cao, Sep 14 '21 at 17:09
Then you need to assign the return result of your `Quick` function back to the name `xxx`, e.g. `xxx = Quick(xxx)`. Then `print(xxx)` will print the sorted list. — Jethro Cao, Sep 14 '21 at 17:14
I tried that and it indeed gives my the correct result, but I'm wondering what's wrong in my Quick(List) that gives me the completely new order of the list when I print it the second time. — QF2QP, Sep 14 '21 at 17:17
I haven't seen quicksort implemented using while loops to shuffle the indices before, but this line looks a bit fishy to me `List[l_idx], List[r_idx] = List[r_idx], List[l_idx]`. What you're doing is mutating the list elements every time that `if` condition is hit. That's what's almost certainly reordering your passed list `xxx`. — Jethro Cao, Sep 14 '21 at 17:20
I think your algorithm return a complete new list, not working on the original list so the original list is not sorted as expect (even its element shuffle a little bit due to the first call of the method, not in recursive one). — Thinhbk, Sep 14 '21 at 18:02

score 0 · Accepted Answer · answered Sep 14 '21 at 18:35

Let's talk about what's happening before moving to the solution. The thrid print output is the list after the first iteration of your algorithm, why is that ? Well when you do List = something you only change what list your variable is refering to and not the list itself. That means List is no longer refering to the list passed as parameter. You could basically just change that statement into an element by element copy like this:

for index, elem in enumerate(Quick(List[0: (l_idx)]) + [List[l_idx]] + Quick(List[(l_idx + 1):])):
    List[index] = elem

Another thing to keep in mind is that, when you use List[:] statement you are creating a new list, and modifications that occur to this slice will not affect the original list. So any changes that happen in the recursive call will be ignored by the original list.

I have modified your method so it works on the original list at every step, for that we will need two aditional parameters, which are the start index and the end index of the current iteration, simulating yout List[:]. Here we go.

def BQuick(List, _from, _to):
    if _to - _from <= 0:
        return List

    pivot = List[_from]

    l_idx = _from
    r_idx = _to

    while l_idx != r_idx:

        while List[l_idx] < pivot and l_idx < r_idx:
            l_idx += 1

        while List[r_idx] > pivot and l_idx < r_idx:
            r_idx -= 1

        if l_idx < r_idx:
            List[l_idx], List[r_idx] = List[r_idx], List[l_idx]

    BQuick(List, _from, l_idx - 1)
    BQuick(List, l_idx + 1, _to)

    return List


def Quick(List):
    return BQuick(List, 0, len(List) - 1)

Since we did all operations on the originall list there is no need to assign at the end to return.

score 0 · Answer 2 · answered Sep 14 '21 at 20:21

The reason is you are assigning a new value to the List (the input variable) inside the function. Hence, the scope of this variable is inside the function, and you cannot see the change over List outside of it (see more details in this post).

However, as mentioned in comments as well, you can assign the result into the xxx, when returning it by xxx = Quick(xxx).

My quick sort code gives me wrong result when printed second time

2 Answers2