Why does input array change inside the recursive function?

Question

I am trying to understand quick search algorithm in pyhton. Here is the code I am working on:

def partition2(a, l, r):
x = a[l]
j = l;
for i in range(l + 1, r + 1):
    if a[i] <= x:
        j += 1
        a[i], a[j] = a[j], a[i]
a[l], a[j] = a[j], a[l]
return j



def randomized_quick_sort(a, l, r):

if l >= r:
    return
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
#use partition3
m = partition2(a, l, r)


randomized_quick_sort(a, l, m - 1);
randomized_quick_sort(a, m + 1, r);

Then I am calling this function defining a variable. For example:

b = [5,1,4]
randomized_quick_sort(b, 0, 2)

MY question is that when I try to print b after the function call, it prints as [1,4,5]. So, how come the value of this array is changing within the function??? It is not a global variable. Whey the local variables inside the function overrides it?? Please help

Lists aren't copied when they're passed into a function. It's one list between all recurses. If you change it, you "change it everywhere". — Carcigenicate
– Carcigenicate, Commented Dec 15, 2018 at 23:44
Thanks for the reply! Quick question: so based on your answer, if it was a integer instead of a list, its value would not change?? — prony
– prony, Commented Dec 15, 2018 at 23:49
@prony It would not. It's for a different reason though. You can't alter a number because they're immutable. Numbers can never change. 1 will always be 1.You're seeing this behavior here because lists themselves are mutable; they can be changed. — Carcigenicate
– Carcigenicate, Commented Dec 15, 2018 at 23:55
Thanks a lot! Have been trying to figure this out for a while! — prony
– prony, Commented Dec 16, 2018 at 0:00

AJ_ · Accepted Answer · 2018-12-16 00:36:05Z

2

When you provide a list as a function argument you are passing a pointer to that list, meaning the parameter a isn't its own array, but a pointer to b.

What you are looking to do is provide only the items of the array b to randomized_quick_sort()

This can be done by making the following adjustment:

randomized_quick_sort (b[:], 0, 2);

Notice b[:] instead of b. Now, when you print b after calling the function you will have the same values as you did before.

You can find more information about this here

answered Dec 16, 2018 at 0:36

AJ_

1,4851 gold badge10 silver badges11 bronze badges

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

Collectives™ on Stack Overflow

Why does input array change inside the recursive function?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related