Don't understand why this quicksort code works

[lupoalberto]

Hi, here there's a quicksort code in Python 3.
It works but my problem is this: i understand what the partition function makes, but i don't understand how the quickSort function is able to change the list if the partition function returns an index, not an element of the list.

Has anyone any hint or advise in order to give me an insight?

def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

def quickSort(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSort(alist,first,splitpoint-1)
       quickSort(alist,splitpoint+1,last)


alist = [4,2,11,1,5]
quickSort(alist,0,len(alist)-1)
print(alist)

Output:
[1, 2, 4, 5, 11]

[nilamo]

It doesn't need to return an element, because it's already moved the items (in place).

[lupoalberto]

It doesn't need to return an element, because it's already moved the items (in place).

Yes, but i don't understand how the QuickSort function is able to move the items in place...(in this case when i say "how" i mean "in which part of the function" this process happens).

I'm studying on the book "Introduction to Algorithms" and it's the first algorithm that i'm not able to understand even after hours..

[nilamo]

Lines 19-21 are where two values are switched (within a while loop), and at the end of the function, lines 23-25, there's another two values switching places.

In a nutshell, leftmark is increased until it's an index to a value that's larger than the value rightmark is an index to, then those two values exchange places. And that's done repeatedly, until no values in the range are larger than any of the values to their right.

I don't think I can explain it very well, so instead, I took your function and added some print functions to it, so we can see what's happening at every step of the process:

def partition(alist, first, last):
    pivotvalue = alist[first]

    leftmark = first + 1
    rightmark = last

    print("Starting partition: pivotvalue={0}".format(pivotvalue))

    done = False
    while not done:

        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark - 1

        print("finding indices complete: leftmark={0}, rightmark={1}".format(
            leftmark, rightmark))

        if rightmark < leftmark:
            done = True
        else:
            print("moving values: alist[{0}]={1} <-> alist[{2}]={3}".format(
                leftmark, alist[leftmark], rightmark, alist[rightmark]))
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp

    print("moving pivotvalue to final position: alist[{0}]={1} <-> alist[{2}]={3}".format(
        first, alist[first], rightmark, alist[rightmark]))
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

    return rightmark


def quickSort(alist, first, last):
    print("Entering quickSort: alist={0}, first={1}, last={2}".format(
        alist, first, last))
    if first < last:

        splitpoint = partition(alist, first, last)
        print("partition() complete, splitpoint={0}".format(splitpoint))
        print()
        quickSort(alist, first, splitpoint - 1)
        quickSort(alist, splitpoint + 1, last)


alist = [4, 2, 11, 1, 5]
quickSort(alist, 0, len(alist) - 1)
print(alist)

Output:
>python spam.py
Entering quickSort: alist=[4, 2, 11, 1, 5], first=0, last=4
Starting partition: pivotvalue=4
finding indices complete: leftmark=2, rightmark=3
moving values: alist[2]=11 <-> alist[3]=1
finding indices complete: leftmark=3, rightmark=2
moving pivotvalue to final position: alist[0]=4 <-> alist[2]=1
partition() complete, splitpoint=2

Entering quickSort: alist=[1, 2, 4, 11, 5], first=0, last=1
Starting partition: pivotvalue=1
finding indices complete: leftmark=1, rightmark=0
moving pivotvalue to final position: alist[0]=1 <-> alist[0]=1
partition() complete, splitpoint=0

Entering quickSort: alist=[1, 2, 4, 11, 5], first=0, last=-1
Entering quickSort: alist=[1, 2, 4, 11, 5], first=1, last=1
Entering quickSort: alist=[1, 2, 4, 11, 5], first=3, last=4
Starting partition: pivotvalue=11
finding indices complete: leftmark=5, rightmark=4
moving pivotvalue to final position: alist[3]=11 <-> alist[4]=5
partition() complete, splitpoint=4

Entering quickSort: alist=[1, 2, 4, 5, 11], first=3, last=3
Entering quickSort: alist=[1, 2, 4, 5, 11], first=5, last=4
[1, 2, 4, 5, 11]

[lupoalberto]

Output:
>python spam.py
Entering quickSort: alist=[4, 2, 11, 1, 5], first=0, last=4
Starting partition: pivotvalue=4
finding indices complete: leftmark=2, rightmark=3
moving values: alist[2]=11 <-> alist[3]=1
finding indices complete: leftmark=3, rightmark=2
moving pivotvalue to final position: alist[0]=4 <-> alist[2]=1
partition() complete, splitpoint=2

Entering quickSort: alist=[1, 2, 4, 11, 5], first=0, last=1
Starting partition: pivotvalue=1
finding indices complete: leftmark=1, rightmark=0
moving pivotvalue to final position: alist[0]=1 <-> alist[0]=1
partition() complete, splitpoint=0

Entering quickSort: alist=[1, 2, 4, 11, 5], first=0, last=-1
Entering quickSort: alist=[1, 2, 4, 11, 5], first=1, last=1
Entering quickSort: alist=[1, 2, 4, 11, 5], first=3, last=4
Starting partition: pivotvalue=11
finding indices complete: leftmark=5, rightmark=4
moving pivotvalue to final position: alist[3]=11 <-> alist[4]=5
partition() complete, splitpoint=4

Entering quickSort: alist=[1, 2, 4, 5, 11], first=3, last=3
Entering quickSort: alist=[1, 2, 4, 5, 11], first=5, last=4
[1, 2, 4, 5, 11]

Thank you so much, now i've understood the whole process/algorithm (damn! is very hard to grasp all these recursions for someone that he's been studying programming for only 3 months like me...) but there is a last thing that i don't understand.

Why all the process that happens in that 2 functions remains outside the functions without any definition of global variables?

I mean, if i code:

def f(x):
    x = x * 2
    return ('a casual expression')

x = 3

f(x)

print(x)

The output is 3, not 6 because x in the function is a local variable and it can't change the global variable x.

I hope i was able to explain my doubt...

[nilamo]

Because the data structure is a list, which is mutable. When you assign something to a variable (x = 42), the old value of the variable still exists, but there's a new binding to the new value. But with lists, the actual variable was never reassigned, the only thing that changed was the contents of the list.

Using your example...

>>> def f(x):
...   x[0] = x[0] * 2
...   return "unrelated string"
...
>>> x = [5, 4, 3, 2, 1, 0]
>>> f(x)
'unrelated string'
>>> x
[10, 4, 3, 2, 1, 0]
>>> # but if we were to re-assign x, instead of using an element...
...
>>> def f(x):
...   x = ['green', 'eggs', 'and', 'spam']
...   return 0
...
>>> x
[10, 4, 3, 2, 1, 0]
>>> f(x)
0
>>> x
[10, 4, 3, 2, 1, 0]

[lupoalberto]

Because the data structure is a list, which is mutable. When you assign something to a variable (x = 42), the old value of the variable still exists, but there's a new binding to the new value. But with lists, the actual variable was never reassigned, the only thing that changed was the contents of the list.

Using your example...

>>> def f(x):
...   x[0] = x[0] * 2
...   return "unrelated string"
...
>>> x = [5, 4, 3, 2, 1, 0]
>>> f(x)
'unrelated string'
>>> x
[10, 4, 3, 2, 1, 0]
>>> # but if we were to re-assign x, instead of using an element...
...
>>> def f(x):
...   x = ['green', 'eggs', 'and', 'spam']
...   return 0
...
>>> x
[10, 4, 3, 2, 1, 0]
>>> f(x)
0
>>> x
[10, 4, 3, 2, 1, 0]

Thank you so much, now i've understood