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

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!!

CodePudding user response：

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.

CodePudding user response：

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).