November 30th, 2013, 07:37 AM

Recursion problem
Hello everyone,
I created a code which should work as a quick_sort to a list of numbers,like shown in this videodelete the part"(delete this part)" :
http://www.youtube.com/watch?v=vxENKlcs2Tw(delete this part)
now, I got a little problem with the Recursion part, it is infinite , and I am not sure how to fix it,
this is my code:
Code:
def partition(lst, start, end):
pos=start
piviot=lst[end]
for j in range (len(lst)1):
if lst[j]<piviot:
lst[pos],lst[j]=lst[j],lst[pos]
pos+=1
lst[pos],lst[len(lst)1]=piviot,lst[pos]
return pos
lst= [42,8, 16, 4, 23, 15]
start=0
end=5
def quick_sort_recursive(lst, start, end):
if lst==[]:
return
piviot=lst[end]
g=partition(lst, start, end)
quick_sort_recursive(lst,0,g)
quick_sort_recursive(lst,g,priviot)
return lst
d=quick_sort_recursive(lst, start, end)
print d
in theory ,the list should have shrinked till it is empty ,
but as you see, it is an infinite loop.
could you help me fix the problem?
thank you very much for your time.
November 30th, 2013, 08:03 AM

I'm really not sure what your recursion is doing but I did notice that you have "priviot" instead of "piviot" in your second internal call.
November 30th, 2013, 11:54 AM

Based on rrashkin's discovery, the infinite recursion happens before the code dealt with the right half of the list. Otherwise you would have found the mistake. The return None statement is wrong:
Code:
>>> print(quick_sort_recursive([], 'unused', 'arguments'))
None
Also the second two arguments to quick_sort_recursive are indexes. You passed one of the list data values, piviot. Again, that was an error to which your algorithm will never arrive. We'll correct these three errors and work from there.
Quick sort review:
Code:
[less than> <values greater than or equal to pivot]
Choose an item from the list. Call it the pivot.
For each item in the list, if the value is less than the pivot fill it in upward from the low bound.
If bigger, fill it in downward from the high index boundary.
We don't know ahead of time where the upward and downward growing sublists will meet.
Repeat the procedure on the two sublists until the size is less than 2.
The resulting list is necessarily ordered.
We need to be careful about which value to choose for next comparison,
and there's another pitfall to avoid as well.
Last edited by b49P23TIvg; November 30th, 2013 at 11:56 AM.
Reason: oops, submit pressed accidentally.
[code]
Code tags[/code] are essential for python code and Makefiles!