Hello I am working on algorithms and I have written a working version of quickSort, see code below:
def quickSort(mylist, l, r):
if l < r:
q = partition(mylist, l, r)
quickSort(mylist, l, q-1)
quickSort(mylist, q+1, r)
def partition(mylist, l, r):
i = l-1
j = l
while j < r:
if mylist[j] < mylist[r]:
i += 1
mylist[i], mylist[j] = mylist[j], mylist[i]
j += 1
mylist[i+1], mylist[j] = mylist[j], mylist[i+1]
return i+1
mylist = [54,26,93,17,77,31,44,55,20,22]
l = 0
r = len(mylist) -1
quickSort(mylist, l, r)
However when I run this I get
UnboundLocalError: local variable 'partition' referenced before assignment
And the fix is to move the definition of the inner function partition
at the top of quickSort
so that it does not call partition
before it is defined.
But I don't understand why, my guess is that inner functions do not "exist" before the outer one is actually executed. Can someone please clarify this point for me ?
In python, you can see functions just as callable variables.
For example you can assign them to variable names, like in the following example:
def example_function():
print("Hello world!")
example_var = example_function
example_var() # call the variable!
Just as you can reassign variables, you can also reassign functions definitions, which means that the definition of a function is not global:
def my_function():
print("first")
my_function() # prints "first"
def my_function():
print("redefined")
my_function() # prints "redefined"
So just as you wouldn't expect something like this ...
# a _not_ defined above
print(a) # even if this worked, should it print "3" or "4"?
a = 3
a = 4
... to work, because the variable is not defined yet, a call of a function, that has not been defined yet, is also not valid.
Like with any other variable, a definition stated in the future is also only valid in that future and it will be obsolete as soon as it is redefined.