Re: Can anyone please help me in understanding the following python code
On May 30, 2:48 pm, bhk...@gmail.com wrote:
Code :
-
def mergeSort(alist):
print(Splitting ,alist)
if len(alist)1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while ilen(lefthalf) and jlen(righthalf):
if lefthalf[i]righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while ilen(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while jlen(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print(Merging ,alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
Output:
---
('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
('Splitting ', [54, 26, 93, 17])
('Splitting ', [54, 26])
('Splitting ', [54])
('Merging ', [54])
('Splitting ', [26])
('Merging ', [26])
('Merging ', [26, 54])
('Splitting ', [93, 17])
('Splitting ', [93])
('Merging ', [93])
('Splitting ', [17])
('Merging ', [17])
('Merging ', [17, 93])
('Merging ', [17, 26, 54, 93])
('Splitting ', [77, 31, 44, 55, 20])
('Splitting ', [77, 31])
('Splitting ', [77])
('Merging ', [77])
('Splitting ', [31])
('Merging ', [31])
('Merging ', [31, 77])
('Splitting ', [44, 55, 20])
('Splitting ', [44])
('Merging ', [44])
('Splitting ', [55, 20])
('Splitting ', [55])
('Merging ', [55])
('Splitting ', [20])
('Merging ', [20])
('Merging ', [20, 55])
('Merging ', [20, 44, 55])
('Merging ', [20, 31, 44, 55, 77])
('Merging ', [17, 20, 26, 31, 44, 54, 55, 77, 93])
[17, 20, 26, 31, 44, 54, 55, 77, 93]
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.
Can anyone please help me out here?
Not in direct answer to your question... Still see if this helps you
to understand mergesorting better.
I generally find that mixing recursion along with imperative
programming makes recursion look difficult.
Imperative programming goes scot-free and recursion gets a bad name!!
So here is a pure recursive/functional solution. Tell me if you
understand it better (or worse!!)
Its written to demonstrate the IDEA of mergesort. Its actual
efficiency is sub-par for various reasons.
-
# merging two lists, both assumed sorted
def merge(a,b):
if a == []: return b
elif b== []: return a
elif a[0] b[0]:
return [a[0]] + merge(a[1:],b)
else:
return [b[0]] + merge(a,b[1:])
# The same as merge above written in pure functional style
def merge1(a,b):
return (b if a == [] else
a if b == [] else
[a[0]] + merge(a[1:],b) if a[0] b[0] else
[b[0]] + merge(a,b[1:])
)
def mergeSort(alist):
if len(alist)1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
return merge1(mergeSort(lefthalf),mergeSort(righthalf) )
else:
return alist
--
http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On Fri, May 31, 2013 at 3:43 PM, Cameron Simpson c...@zip.com.au wrote: On 30May2013 21:54, bhk...@gmail.com bhk...@gmail.com wrote: | One final question, Is there a way to edit the message once it has been posted? Essentially, no. If there's some error in a post, reply to it yourself with a correction. Transparency is a good thing. Revisionist history pretty much is not. Once your email or newsgroup post is sent, assume that it's also been received; at very least, you won't be far wrong. You'll sometimes see a response within minutes from someone who saw your post within seconds. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On Thu, May 30, 2013 at 7:48 PM, bhk...@gmail.com wrote: 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. When it says Splitting with a single-element list, it then immediately prints Merging and returns (because all the rest of the code is guarded by the 'if'). Execution then continues where it left off, in the parent. One good way to get an idea of what's going on is to add a recursion depth parameter. Keep all the rest of the code the same, but change the print and recursion lines to be like this: def mergeSort(alist,depth): print(%*cSplitting %r%(depth*2,' ',alist)) # ... mergeSort(lefthalf,depth+1) mergeSort(righthalf,depth+1) # ... print(%*cMerging %r%(depth*2,' ',alist)) mergeSort(alist,0) That'll indent everything according to the depth of the call stack. (Also, I changed your 'print's to be compatible with Python 2 and Python 3; you seemed to have Python 3 style function calls and a Python 2 interpreter.) Hopefully that'll make clearer what's going on! ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
bhk755 at gmail.com writes: 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. Maybe you should tell us first what output you would have expected. It's not really clear from your question what confuses you. Doesn't the algorithm do what it's supposed to do? When does the function start from i=0, j=0, k=0 ? What exactly is the output then ? Maybe you are confused by the fact that the algorithm is recursive twice. It first goes through the lefthand branch, then only on its way out it works on the righthand branch. So the recursion through mergeSort is not started only once as you say, but twice (after finishing the recursion through mergeSort(lefthand), another recursion is kicked off by calling mergeSort(righthand). Best, Wolfgang -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
Thanks for the reply Chris. I am newbie to python, so please excuse me if I am asking chilly questions. Can you please explain more about the following sentence. When it says Splitting with a single-element list, it then immediately prints Merging and returns (because all the rest of the code is guarded by the 'if'). Execution then continues where it left off, in the parent. Because I am not sure how the control can go back to top of the function unless there is no loops there. Also, Can you please let me know how did you found out that I am using Python 2 Interpreter. Bharath -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
bhk755 at gmail.com writes: Thanks for the reply Chris. I am newbie to python, so please excuse me if I am asking chilly questions. Can you please explain more about the following sentence. When it says Splitting with a single-element list, it then immediately prints Merging and returns (because all the rest of the code is guarded by the 'if'). Execution then continues where it left off, in the parent. Because I am not sure how the control can go back to top of the function unless there is no loops there. It doesn't. The function simply returns and execution resumes in the parent, i.e. in the calling function at depth-1, where it left off. In Python, a return None is implied when a function falls off its end. Also, Can you please let me know how did you found out that I am using Python 2 Interpreter. print as a statement (without parentheses) only works in Python 2, in Python 3 print is a function. Bharath -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On Thu, May 30, 2013 at 8:19 PM, bhk...@gmail.com wrote:
Thanks for the reply Chris.
I am newbie to python, so please excuse me if I am asking chilly questions.
All questions are welcome!
Can you please explain more about the following sentence.
When it says Splitting with a single-element list, it then
immediately prints Merging and returns (because all the rest of the
code is guarded by the 'if'). Execution then continues where it left
off, in the parent.
The code goes like this:
1) Print Splitting
2) If there's more than one element in the list:
2a) Divide the list in half
2b) Call self on each half
2c) Merge
3) Print Merging
In step 2b, all the steps from 1 through 3 are executed again (twice).
Soon, those calls will just output Splitting followed by Merging;
and then we go back to 2c. That's why it *seems* that the code goes
from 3 to 2c. You'll notice that the call depth decreases when this
happens.
Because I am not sure how the control can go back to top of the function
unless there is no loops there.
Also, Can you please let me know how did you found out that I am using Python
2 Interpreter.
That one is actually based on my crystal ball. Here on python-list, we
issue them to all our top respondents; they're extremely useful. I'll
let you in on part of the secret of how this works, though.
In Python 2, 'print' is (by default) a statement. When you give it
something in parentheses, it sees a tuple:
print(Splitting ,alist)
('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
In Python 3, 'print' is a function. It takes arguments, and prints out
each argument, separated by spaces.
print(Splitting ,alist)
Splitting [17, 20, 26, 31, 44, 54, 55, 77, 93]
You can make Python 2 behave the same way by putting this at the top
of your program:
from __future__ import print_function
ChrisA
--
http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On 30 May 2013 10:48, bhk...@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?
--
http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On 30 May 2013 11:19, bhk...@gmail.com wrote: Also, Can you please let me know how did you found out that I am using Python 2 Interpreter. Do you have access to a Python3 interpreter? If so, try running it and your output will look like: Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] Splitting [54, 26, 93, 17] Splitting [54, 26] Splitting [54] Merging [54] Splitting [26] Merging [26] ... BLAH BLAH BLAH Which is obviously much nicer. This is how Chris knew the code was written for Python3. Therefore I would suggest you use Python3 - not all code runs on both! The proper way to write the prints for Python2 is without the brackets: print Merging ,alist But the methods Chris and I have used work the same on both so are probably better in this case. They're more complicated, though. -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
Thanks Chris, Wolfgang and Joshua for your replies. --- In step 2b, all the steps from 1 through 3 are executed again (twice). Soon, those calls will just output Splitting followed by Merging; and then we go back to 2c. That's why it *seems* that the code goes from 3 to 2c. You'll notice that the call depth decreases when this happens Chris, Can you please let me know what makes the control of the program code go to 2c after the output Merging. Also, please look into the following output, before calling main mergesort Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] left half before split [54, 26, 93, 17] right half before split [77, 31, 44, 55, 20] Splitting [54, 26, 93, 17] left half before split [54, 26] right half before split [93, 17] Splitting [54, 26] left half before split [54] right half before split [26] Splitting [54] Merging [54] Splitting [26] Merging [26] HERE AFTER SPLIT left half after split [54] right half after split [26] Merging [26, 54] Splitting [93, 17] left half before split [93] right half before split [17] Splitting [93] Merging [93] Splitting [17] Merging [17] HERE AFTER SPLIT left half after split [93] right half after split [17] Merging [17, 93] HERE AFTER SPLIT left half after split [26, 54] right half after split [17, 93] Merging [17, 26, 54, 93] Splitting [77, 31, 44, 55, 20] left half before split [77, 31] right half before split [44, 55, 20] Splitting [77, 31] left half before split [77] right half before split [31] Splitting [77] Merging [77] Splitting [31] Merging [31] HERE AFTER SPLIT left half after split [77] right half after split [31] Merging [31, 77] Splitting [44, 55, 20] left half before split [44] right half before split [55, 20] Splitting [44] Merging [44] Splitting [55, 20] left half before split [55] right half before split [20] Splitting [55] Merging [55] Splitting [20] Merging [20] HERE AFTER SPLIT left half after split [55] right half after split [20] Merging [20, 55] HERE AFTER SPLIT left half after split [44] right half after split [20, 55] Merging [20, 44, 55] HERE AFTER SPLIT left half after split [31, 77] right half after split [20, 44, 55] Merging [20, 31, 44, 55, 77] HERE AFTER SPLIT left half after split [17, 26, 54, 93] right half after split [20, 31, 44, 55, 77] Merging [17, 20, 26, 31, 44, 54, 55, 77, 93] after calling main mergesort [17, 20, 26, 31, 44, 54, 55, 77, 93] - In the above output, the control goes to HERE AFTER SPLIT after the Merging statement which is of-course the last statement in the function.On what condition this is happening. Ideally as per my understanding, after the last statement of a function the control should come out of the function. Please correct me if I am wrong here. There is something with respect-to functions in python that I am not able to understand. -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On Thursday, May 30, 2013 6:09:20 PM UTC+5:30, bhk...@gmail.com wrote: Thanks Chris, Wolfgang and Joshua for your replies. --- In step 2b, all the steps from 1 through 3 are executed again (twice). Soon, those calls will just output Splitting followed by Merging; and then we go back to 2c. That's why it *seems* that the code goes from 3 to 2c. You'll notice that the call depth decreases when this happens Chris, Can you please let me know what makes the control of the program code go to 2c after the output Merging. Also, please look into the following output for the same program with more print statements, -- before calling main mergesort Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] left half before split [54, 26, 93, 17] right half before split [77, 31, 44, 55, 20] Splitting [54, 26, 93, 17] left half before split [54, 26] right half before split [93, 17] Splitting [54, 26] left half before split [54] right half before split [26] Splitting [54] Merging [54] Splitting [26] Merging [26] HERE AFTER SPLIT left half after split [54] right half after split [26] Merging [26, 54] Splitting [93, 17] left half before split [93] right half before split [17] Splitting [93] Merging [93] Splitting [17] Merging [17] HERE AFTER SPLIT left half after split [93] right half after split [17] Merging [17, 93] HERE AFTER SPLIT left half after split [26, 54] right half after split [17, 93] Merging [17, 26, 54, 93] Splitting [77, 31, 44, 55, 20] left half before split [77, 31] right half before split [44, 55, 20] Splitting [77, 31] left half before split [77] right half before split [31] Splitting [77] Merging [77] Splitting [31] Merging [31] HERE AFTER SPLIT left half after split [77] right half after split [31] Merging [31, 77] Splitting [44, 55, 20] left half before split [44] right half before split [55, 20] Splitting [44] Merging [44] Splitting [55, 20] left half before split [55] right half before split [20] Splitting [55] Merging [55] Splitting [20] Merging [20] HERE AFTER SPLIT left half after split [55] right half after split [20] Merging [20, 55] HERE AFTER SPLIT left half after split [44] right half after split [20, 55] Merging [20, 44, 55] HERE AFTER SPLIT left half after split [31, 77] right half after split [20, 44, 55] Merging [20, 31, 44, 55, 77] HERE AFTER SPLIT left half after split [17, 26, 54, 93] right half after split [20, 31, 44, 55, 77] Merging [17, 20, 26, 31, 44, 54, 55, 77, 93] after calling main mergesort [17, 20, 26, 31, 44, 54, 55, 77, 93] --- In the above output, the control goes to HERE AFTER SPLIT after the Merging statement which is of-course the last statement in the function.On what condition this is happening. Ideally as per my understanding, after the last statement of a function the control should come out of the function. Please correct me if I am wrong here. There is something with respect-to functions in python that I am not able to understand. -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On Thursday, May 30, 2013 6:09:20 PM UTC+5:30, bhk...@gmail.com wrote: Thanks Chris, Wolfgang and Joshua for your replies. --- In step 2b, all the steps from 1 through 3 are executed again (twice). Soon, those calls will just output Splitting followed by Merging; and then we go back to 2c. That's why it *seems* that the code goes from 3 to 2c. You'll notice that the call depth decreases when this happens Chris, Can you please let me know what makes the control of the program code go to 2c after the output Merging. Also, please look into the following output for the same program with more print statements, -- before calling main mergesort Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] left half before split [54, 26, 93, 17] right half before split [77, 31, 44, 55, 20] Splitting [54, 26, 93, 17] left half before split [54, 26] right half before split [93, 17] Splitting [54, 26] left half before split [54] right half before split [26] Splitting [54] Merging [54] Splitting [26] Merging [26] HERE AFTER SPLIT left half after split [54] right half after split [26] Merging [26, 54] Splitting [93, 17] left half before split [93] right half before split [17] Splitting [93] Merging [93] Splitting [17] Merging [17] HERE AFTER SPLIT left half after split [93] right half after split [17] Merging [17, 93] HERE AFTER SPLIT left half after split [26, 54] right half after split [17, 93] Merging [17, 26, 54, 93] Splitting [77, 31, 44, 55, 20] left half before split [77, 31] right half before split [44, 55, 20] Splitting [77, 31] left half before split [77] right half before split [31] Splitting [77] Merging [77] Splitting [31] Merging [31] HERE AFTER SPLIT left half after split [77] right half after split [31] Merging [31, 77] Splitting [44, 55, 20] left half before split [44] right half before split [55, 20] Splitting [44] Merging [44] Splitting [55, 20] left half before split [55] right half before split [20] Splitting [55] Merging [55] Splitting [20] Merging [20] HERE AFTER SPLIT left half after split [55] right half after split [20] Merging [20, 55] HERE AFTER SPLIT left half after split [44] right half after split [20, 55] Merging [20, 44, 55] HERE AFTER SPLIT left half after split [31, 77] right half after split [20, 44, 55] Merging [20, 31, 44, 55, 77] HERE AFTER SPLIT left half after split [17, 26, 54, 93] right half after split [20, 31, 44, 55, 77] Merging [17, 20, 26, 31, 44, 54, 55, 77, 93] after calling main mergesort [17, 20, 26, 31, 44, 54, 55, 77, 93] --- In the above output, the control goes to HERE AFTER SPLIT after the Merging statement which is of-course the last statement in the function.On what condition this is happening. Ideally as per my understanding, after the last statement of a function the control should come out of the function. Please correct me if I am wrong here. There is something with respect-to functions in python that I am not able to understand. -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On Thu, May 30, 2013 at 10:39 PM, bhk...@gmail.com wrote: Chris, Can you please let me know what makes the control of the program code go to 2c after the output Merging. It goes like this: 1. [eight element list] 2a. [eight element list] 2b. 1. [four element list] 2b. 2a. [four element list] 2b. 2b.1. [two element list] 2b. 2b.2a. [two element list] 2b. 2b.2b. [two element list] 2b. 2b.2b.1. [one element list] 2b. 2b.2b.2. [one element list] 2b. 2b.2b.3. [one element list] 2b. 2b.2c. [two element list] 2b. 2b.3. [two element list] ... etc etc etc ... Notice how control actually flows from 1, to 2a, to 2b, to 2c, but in between, it goes back to 1? That's recursion. There are four separate function calls here, which you can see going down the page. Each time it gets to step 2b, a whole new thread starts, and the previous one doesn't do anything till the inner one reaches step 3 and finishes. That's why the indented output can help; eyeball them going down and you'll see that they don't do anything until the inner one finishes. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
Thanks Chris, Wolfgang and Joshua for your replies. In step 2b, all the steps from 1 through 3 are executed again (twice). Soon, those calls will just output Splitting followed by Merging; and then we go back to 2c. That's why it *seems* that the code goes from 3 to 2c. You'll notice that the call depth decreases when this happens Chris, Can you please let me know what makes the control of the program code go to 2c after the output Merging. Also, please look into the following output for the same program with more print statements, -- before calling main mergesort Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] left half before split [54, 26, 93, 17] right half before split [77, 31, 44, 55, 20] Splitting [54, 26, 93, 17] left half before split [54, 26] right half before split [93, 17] Splitting [54, 26] left half before split [54] right half before split [26] Splitting [54] Merging [54] Splitting [26] Merging [26] HERE AFTER SPLIT left half after split [54] right half after split [26] Merging [26, 54] Splitting [93, 17] left half before split [93] right half before split [17] Splitting [93] Merging [93] Splitting [17] Merging [17] HERE AFTER SPLIT left half after split [93] right half after split [17] Merging [17, 93] HERE AFTER SPLIT left half after split [26, 54] right half after split [17, 93] Merging [17, 26, 54, 93] Splitting [77, 31, 44, 55, 20] left half before split [77, 31] right half before split [44, 55, 20] Splitting [77, 31] left half before split [77] right half before split [31] Splitting [77] Merging [77] Splitting [31] Merging [31] HERE AFTER SPLIT left half after split [77] right half after split [31] Merging [31, 77] Splitting [44, 55, 20] ft half before split [44] ght half before split [55, 20] Splitting [44] Merging [44] Splitting [55, 20] eft half before split [55] ight half before split [20] Splitting [55] Merging [55] Splitting [20] Merging [20] HERE AFTER SPLIT left half after split [55] right half after split [20] Merging [20, 55] HERE AFTER SPLIT left half after split [44] right half after split [20, 55] Merging [20, 44, 55] HERE AFTER SPLIT left half after split [31, 77] right half after split [20, 44, 55] Merging [20, 31, 44, 55, 77] HERE AFTER SPLIT left half after split [17, 26, 54, 93] right half after split [20, 31, 44, 55, 77] Merging [17, 20, 26, 31, 44, 54, 55, 77, 93] after calling main mergesort [17, 20, 26, 31, 44, 54, 55, 77, 93] --- In the above output, the control goes to HERE AFTER SPLIT after the Merging statement which is of-course the last statement in the function.On what condition this is happening. Ideally as per my understanding, after the last statement of a function the control should come out of the function. Please correct me if I am wrong here. There is something with respect-to functions in python that I am not able to understand. -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On 05/30/2013 08:42 AM, bhk...@gmail.com wrote: SNIP lots of double-spaced googlegroups nonsense. Please read this http://wiki.python.org/moin/GoogleGroupsPython In the above output, the control goes to HERE AFTER SPLIT after the Merging statement which is of-course the last statement in the function.On what condition this is happening. Ideally as per my understanding, after the last statement of a function the control should come out of the function. Please correct me if I am wrong here. There is something with respect-to functions in python that I am not able to understand. I think you misunderstand recursion. And you should study it in a simpler example before trying to tackle that sort function. After the last statement of a function, or after an explicit return statement, the function does indeed return control to whoever called it. And if the call was in the middle of some other function, that's the place where execution will continue. Functions may nest this way to pretty large depths of complexity. If you're not sure you understand that, we should stop here. So in your reply, tell me if you can readily grasp function dfunc() calling cfunc(), which calls bfunc(), which calls afunc(). When afunc() returns, you'll be right in the middle of bfunc(), right after the call was made. Now to recursion. One can write a function which solves a particular problem by doing some of the work, but by calling on other functions which solve simpler subproblems. Recursion comes in when those other functions are simply instances of the same one. So instead of dfunc() calling cfunc(), we have rfunc() calling rfunc() calling rfunc() calling rfunc(). Let's take a classic problem for explaining recursion: factorial. We can write a simple function that solves the problem for 0: def afunc(n): if n == 0: return 1 else: throw-some-exception Silly function, I know. Now let's write one that solves it for one. def bfunc(n): if n == 1: return 1 * afunc(n-1) else: throw-some-exception Now for two: def bfunc(n): if n == 2: return 2 * bfunc(n-1) else: throw-some-exception Notice that each function calls the one above it to solve the simpler problem. Now if we wanted this to work for n=100, it would get really tedious. So let's see if we can write one function that handles all of these cases. def rfunc(n): if n == 0: return 1 else: return n * rfunc(n-1) Now if we call this with n==3, it'll make the zero check, then it'll call another function with the value 2. that one will in turn call another function with the value 1. And so on. So this function calls itself, as we say recursively. Now, for this simple case, we could have used a simple loop, or just called the library function. But it's a simple enough example to follow in its entirety (if I've been clear in my writing). Your mergeSort() function calls itself recursively, and each time it does, it passes a *smaller* list to be sorted. Eventually the calls recurse down to a list of size 1, which is already sorted by definition. The check for that is the line if len(alist)1: near the beginning of the function. That's analogous to my if n==0 line, although to match it most directly, I could have reversed the if/else and written the test as if n!=0 Chris showed you how to change your output so you could see the nesting levels. I have done that sort of thing in the past, and found it very useful. But first you have to understand nested functions, and simple recursion. -- DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
Got It!!!, Finally. Thanks Dave So, the control goes back to the place after the recursive function is called once the no. of element is equal to one and starts merging after which it will again start to split the remaining items. Thank you Chris for your multiple explanations. It was also very useful. One final question, Is there a way to edit the message once it has been posted? -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
Got It!!!, Finally. Thanks Dave So, the control goes back to the place after the recursive function is called once the no. of element is equal to one and starts merging after which it will again start to split the remaining items. Thank you Chris for your multiple explanations. One final question, Is there a way to edit the message once it has been posted? -- http://mail.python.org/mailman/listinfo/python-list
Re: Can anyone please help me in understanding the following python code
On 30May2013 21:54, bhk...@gmail.com bhk...@gmail.com wrote: | One final question, Is there a way to edit the message once it has been posted? Essentially, no. If there's some error in a post, reply to it yourself with a correction. Transparency is a good thing. Revisionist history pretty much is not. -- Cameron Simpson c...@zip.com.au Well, it's one louder, isn't it? It's not ten. You see, most blokes are gonna be playing at ten, you're on ten here, all the way up, all the way up, all the way up, you're on ten on your guitar, where can you go from there? Where? Nowhere, exactly. What we do is, if we need that extra push over the cliff, you know what we do? Eleven. Exactly. One louder. - Nigel Tufnel, _This Is Spinal Tap_ -- http://mail.python.org/mailman/listinfo/python-list
