Can anyone please help me in understanding the following python code
Joshua Landau
joshua.landau.ws at gmail.com
Thu May 30 07:03:22 EDT 2013
On 30 May 2013 10:48, <bhk755 at gmail.com> wrote:
> Question:
> ---------
> Function mergeSort is called only once, but it is getting recursively executed after the printing the last statement "print("Merging ",alist)". But don't recursion taking place except at these places "mergeSort(lefthalf), mergeSort(righthalf)"
>
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure how.
Here's some different code; it does the same thing but in a less weird way:
##########################
def mergeSort(alist, depth=1):
# If the piece we have to sort is [i] or [], then we have no sorting to do
if len(alist) <= 1:
# Returning what we were given
# Make a new list from it, though, because we are nice
print("{padding}return {list}\n".format(padding=" "*depth*8,
list=alist))
return alist[:]
# Split along the middle
mid = len(alist)//2
# We have two halves
lefthalf = alist[:mid]
righthalf = alist[mid:]
# Which we sort, so we have two sorted halves
print("{padding}lefthalf = mergesort({list})\n".format(padding="
"*depth*8, list=lefthalf))
lefthalf = mergeSort(lefthalf, depth+1)
print("{padding}righthalf = mergesort({list})\n".format(padding="
"*depth*8, list=righthalf))
righthalf = mergeSort(righthalf, depth+1)
# We want to return a sorted "alist" from our two lists
# We'll add the items to here
new_list = []
# We'll go through adding the smallest to new_list
while lefthalf and righthalf:
# Lefthalf has the smaller item, so we "pop" it off into new_list
if lefthalf[0] < righthalf[0]:
new_list.append(lefthalf.pop(0))
# Righthalf has the smaller item, so we "pop" it off into new_list
else:
new_list.append(righthalf.pop(0))
# One of our lists isn't empty, so just add them on
new_list += lefthalf + righthalf
print("{padding}return {list}\n".format(padding=" "*depth*8, list=new_list))
return new_list
print("Start mergesort({list}):\n".format(list=[2, 4, 0, 1]))
sorted_list = mergeSort([2, 4, 0, 1])
print("Our final result: {list}".format(list=sorted_list))
##########################
And it gives
##########################
Start mergesort([2, 4, 0, 1]):
lefthalf = mergesort([2, 4])
lefthalf = mergesort([2])
return [2]
righthalf = mergesort([4])
return [4]
return [2, 4]
righthalf = mergesort([0, 1])
lefthalf = mergesort([0])
return [0]
righthalf = mergesort([1])
return [1]
return [0, 1]
return [0, 1, 2, 4]
Our final result: [0, 1, 2, 4]
##########################
Hopefully this code is a little easier to understand - the original
changes the list while it is running the algorithm and mine makes new
lists. The algorithm is very similar, and what you learn applies to
both.
You can see in the output (thanks Chris Angelico) that the main
function is always running. It runs *two* other instances: lefthalf
and righthalf.
So the "mergesort([2, 4, 0, 1])" runs "lefthalf = mergesort([2, 4])"
"mergesort([2, 4])" runs "lefthalf = mergesort([2])"
"mergesort([2])" gives back [2] to "mergesort([2, 4])"
"mergesort([2, 4])" goes "OH! I can continue now" and runs "righthalf
= mergesort([4])"
"mergesort([4])" gives back [4] to "mergesort([2, 4])"
"mergesort([2, 4])" goes "OH! I can continue now" and gives back [2,
4] to "mergesort([2, 4, 0, 1])"
"mergesort([2, 4, 0, 1])" goes "OH! I can continue now" and runs
"righthalf = mergesort([0, 1])"
"mergesort([0, 1])" runs "lefthalf = mergesort([0])"
"mergesort([0])" gives back [0] to "mergesort([0, 1])"
"mergesort([0, 1])" goes "OH! I can continue now" and runs "righthalf
= mergesort([1])"
"mergesort([1])" gives back [1] to "mergesort([0, 1])"
"mergesort([0, 1])" goes "OH! I can continue now" and gives back [0,
1] to "mergesort([2, 4, 0, 1])"
"mergesort([2, 4, 0, 1])" goes "OH! I can continue now" and gives back
[0, 1, 2, 4]
DONE.
Does that help you see the flow?
Exactly the same flow happens for your code. The difference is that
instead of returning a list, mergesort *sorts* a list, and then that
is used to replace items in the original list. Personally, their way
is a little silly (and mine is inefficient, so use neither).
Question: Why did you rewrite the code?
Answer: Revising is boring.
Question: Sometimes the function execution directly starts from
i=0,j=0,k=0 . Not sure how.
Answer: That's not a question. Anyhow:
i, j and k are LOCAL to a function. "mergesort([2, 4, 0, 1])" has a
different i, j and k than "mergesort([0, 1])", They never use each
other's i, j and k. Hence for each recursion they run "i=0, j=0, k=0"
and they are set to 0 within the function.
Does this help?
More information about the Python-list
mailing list