python list and quick sort, reference or pointer?

Question

I am a python new comer.

Recently I am implementing quicksort in python.

I heard the variable type called list is mutable, so any changes done to this will take affect in place. However, it is not in my place.

Here is my case, the function called alpartition has been tested and it proved to me that this function can work.(As it is required in the quick sort algorithm ). And the function called test is a recursion one. As we can see from the printed result, all parties of the variable called a has been modified. But it just don't come in together. It seems to me that one change has been done to this variable.

I used to a C programmer and I kind of treat list as a collection of pointer, I guess the fault is due to the misuse of the slicing technique.

Thanks a lot for your kindly help.

Here is the function :

__author__ = 'tk'
import random
def alpartition(my_str):

    signal = 0
    i = 0
    j = len(my_str)

    while i < j:
            if signal == 0 :
                while 1:
                    j = j - 1
                    if my_str[j] <= my_str[i]:
                        break
                signal = 1
            else:
                while 1:
                    i = i + 1
                    if my_str[j] <= my_str[i]:
                        break
                signal = 0
            my_str[j],my_str[i] = my_str[i],my_str[j]
    my_str[j],my_str[i] = my_str[i],my_str[j]
    return i


def test(my_str):
    if len(my_str)>1:
        tick = alpartition(my_str)
        print my_str,my_str[0:tick:],my_str[tick+1::],tick #We can see that my_str has correctly been modified 
        if tick > 0 :
            test(my_str[0:tick:])
            test(my_str[tick+1::])
a= [86, 44, 31, 7, 9, 90, 93, 12, 59, 34]
test(a)
print a

Here is the result: The first variable to be printed is the partitioned variable, and it is partitioned by the variable called tick whose value will be printed at the fourth position. The second and third variable is just the partial variable.

[34, 44, 31, 7, 9, 59, 12, 86, 93, 90] [34, 44, 31, 7, 9, 59, 12] [93, 90] 7
[12, 9, 31, 7, 34, 59, 44] [12, 9, 31, 7] [59, 44] 4
[7, 9, 12, 31] [7, 9] [31] 2
[7, 9] [] [9] 0
[44, 59] [44] [] 1
[90, 93] [90] [] 1
[34, 44, 31, 7, 9, 59, 12, 86, 93, 90]

My question is why the final result is identical to the first printed variable at the very beginning. Why all the changes haven't been done to this variable?

Answer 1

Python lists are immutable, however, the slicing operation returns a new list every time. This is why a common idiom in python to get a new copy of a list is to slice it with [:]. This returns a new list containing all the items of the old lost.

However, there is a subtle point about the mutability or immutability of the elements inside the list. In your case, since they are numbers and are immutable, the new list returned from slicing is an entirely new list and changing it will not affect the original list:

>>> my_list = [1, 2, 3]        # Create a list with three numbers
>>> my_other_list = my_list[:] # Slice the original list to get a copy
>>> my_other_list[0] = 42      # Change the first element of the new list
>>> my_other_list, my_list     # See the two lists side by side
([42, 2, 3], [1, 2, 3])        # The change to the new list did not effect the original list

But, if the content of the first list were of an mutable type, say a list. Then the story would be different:

>>> my_list = [[1], [2], [3]]
>>> my_other_list = my_list[:]
>>> my_other_list[0].append(42)
>>> my_other_list, my_list
([[1, 42], [2], [3]], [[1, 42], [2], [3]])

Suffice it to say that in your case the elements of your list are numbers and they are immutable. So, every time you slice the original list, you are getting a new list and any changes you make to it has no effect on the original list.