Usually, in case of doubt, use a debugger or print statements:
def selection_sort(lst,start,end):
"""sort the lst from selection start to end"""
print lst, start, end
if len(lst)==1:
print "list of size 1"
return lst
elif lst=="":
print "list is an emtpy string"
return ""
else:
print "selection_sort(",lst,start+1,end,")"
return lst[:start]+selection_sort(lst,start+1,end)
Let's see what happens:
>>> a=[1,3,5,2]
>>> b=1
>>> c=3
>>> selection_sort(a,b,c)
[1, 3, 5, 2] 1 3
selection_sort( [1, 3, 5, 2] 2 3 )
[1, 3, 5, 2] 2 3
selection_sort( [1, 3, 5, 2] 3 3 )
[1, 3, 5, 2] 3 3
selection_sort( [1, 3, 5, 2] 4 3 )
[1, 3, 5, 2] 4 3
selection_sort( [1, 3, 5, 2] 5 3 )
[1, 3, 5, 2] 5 3
selection_sort( [1, 3, 5, 2] 6 3 )
[1, 3, 5, 2] 6 3
selection_sort( [1, 3, 5, 2] 7 3 )
[1, 3, 5, 2] 7 3
Etc,etc,etc
It seems that you are incrementing the start variable.
This is done in the line of code:
return lst[:start]+selection_sort(lst,start+1,end)
If we arrive to this line of code is because of the conditions of the
two previous "if":
- The list is not of size 1.
- The list is not an empty string.
Actually, when you do a recursion function you must make sure you have
an exit condition. And your function does not have.
If you want your function to end, it must arrive at one point to a
size of 1 or to be an empty string.
I did this by changing the line:
return lst[:start]+selection_sort(lst,start+1,end)
into the line:
return lst[:start]+selection_sort(lst[start:],start+1,end)
Oh... I am also wandering why you look for an empty string. You would
be better off by substituing "" by an empty list []
elif lst==[]:
print "list is emtpy"
return []
You can even put togheter this line with the if len(lst)==1: line:
if len(lst)==1:
print "list of size 1"
return lst
elif lst==[]:
print "list is emtpy"
return []
becomes
if 0<len(lst)<2:
return lst
It's not the good implementation of your algorithm (because I don't
know what you intend to do...), but because each time our lst becomes
tinier, the recursive function will not enter an infinite loop:
>>> def selection_sort(lst,start,end):
"""sort the lst from selection start to end"""
print lst, start, end
if 0<=len(lst)<2:
print "list of size 1 or less"
return lst
else:
print "selection_sort(",lst,start+1,end,")"
return lst[:start]+selection_sort(lst[start:],start+1,end)
>>> selection_sort_modified(a,b,c)
[1, 3, 5, 2] 1 3
selection_sort( [1, 3, 5, 2] 2 3 )
[3, 5, 2] 2 3
selection_sort( [3, 5, 2] 3 3 )
[2] 3 3
list of size 1
[1, 3, 5, 2]
>>> a=[1,6,2,2,5,3,9,0,3,4]
>>> b=3
>>> c=8
>>> selection_sort(a,b,c)
[1, 6, 2, 2, 5, 3, 9, 0, 3, 4] 3 8
selection_sort( [1, 6, 2, 2, 5, 3, 9, 0, 3, 4] 4 8 )
[2, 5, 3, 9, 0, 3, 4] 4 8
selection_sort( [2, 5, 3, 9, 0, 3, 4] 5 8 )
[0, 3, 4] 5 8
selection_sort( [0, 3, 4] 6 8 )
[] 6 8
list of size 1 or less
[1, 6, 2, 2, 5, 3, 9, 0, 3, 4]
Hope that helps,
G
On Tue, 07 Dec 2004 12:37:20 +0800, Lin Jin <[EMAIL PROTECTED]> wrote:
> hello,tutors:
> i am working on the recursion of selection sort,and my code is:
> def selection_sort(lst,start,end):
> """sort the lst from selection start to end"""
> if len(lst)==1:
> return lst
> elif lst=="":
> return ""
> else:
> return lst[:start]+selection_sort(lst,start+1,end)
> a=[1,3,5,2]
> b=1
> c=3
> print selection_sort(a,b,c)
>
> but it seems not working when i call the function,anyone could tell me that
> what i did wrong with my code?
>
> _________________________________________________________________
> äçäçäæåççåéäççâ MSN Hotmailã
> http://www.hotmail.com
>
> _______________________________________________
> Tutor maillist - [EMAIL PROTECTED]
> http://mail.python.org/mailman/listinfo/tutor
>
_______________________________________________
Tutor maillist - [EMAIL PROTECTED]
http://mail.python.org/mailman/listinfo/tutor
